Forum

> > CS2D > Scripts > ai: nearest breakable
Forums overviewCS2D overview Scripts overviewLog in to reply

English ai: nearest breakable

3 replies
To the start Previous 1 Next To the start

old ai: nearest breakable

EnderCrypt
User Off Offline

Quote
hi im trying to make bot, and i wonder if theres an efficient way of getting id of nearest breakable, eithere in a rectangulare area or direct?

edit: is there any hook to se if a breakable entry thing has been damaged
edited 1×, last 26.06.11 03:42:45 pm

old Re: ai: nearest breakable

Lee
Moderator Off Offline

Quote
The naive implementation is as follows.

You get the size of the map, and iterate over every single tile and filter out tiles that do not fall within your square. The code looks something like this:

1
2
3
4
5
6
7
8
local rect = {x, y, width, height}

xsize, ysize = (1+map("xsize")), (1+map("ysize"))
output = {}
for i = rect.x+rect.y*xsize, (rect.x + rect.width)+(rect.y + rect.height)*xsize -1 do
	local x,y = i%ysize, math.floor(i/ysize)
	if entity(x, y, "type") == 25 then table.insert(output, {x,y}) end
end

This is useful for cases where the entity : tile ratio is relatively high, IE the number of entities is almost equal to the total number of tiles in the selected region, in which case the lower bound time complexity of any algorithm must approach O(width*height).

However, in most cases, there are far fewer entities than tiles. (IE: de_cs2d has only 20 entities while there are 574 tiles, which means that only 3% of the tiles contain entities, and this is just a small map) In maps with large open spaces, it may no longer be feasible to check for breakable entities in a small confined rectangle while iterating over every tile will seem inefficient, especially if the map is anything larger than medium sized.

In cases where the spread of entities is sparse and the total count << tile count, then we can speed up the average lookup time by caching all of the entities at the start of the game.

1
2
3
4
5
6
xsize, ysize = (1+map("xsize")), (1+map("ysize"))
cache = {}
for i = 0, xsize * ysize -1 do
	local x,y = i%ysize, math.floor(i/ysize)
	if entity(x,y,"type") == 25 then table.insert(cache, {x,y}) end
end

and then iterating through this list instead.

Also, if you have thousands of entities and want to do look up in only a specific rectangular region, there's a O(log n) data structure for such operations: http://en.wikipedia.org/wiki/Quadtree

Here's a functional implementation in ml: https://gist.github.com/1047975

old Re: ai: nearest breakable

DC
Admin Off Offline

Quote
to answer your edit: if you mean damage=break then cs2d lua hook break - if you are talking about damaging without breaking: nope, no hook for that.
To the start Previous 1 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview