3 replies to this topic

[TMGeorge]

Hi there, even I read a lot of articles about A* but they always seem to deal with units which fit into one block. So maybe you can give me a hint or point me to an article where A* deals with various unit sizes e.g. men, vehicles ... The only Idea I have is that every block contains the distance to the next blocked block so that depending of the unit halfDiameter it can be determined if the unit could go to this block or not. Sceneraio is RTS. rgds tmg

[Crazyfool]

Couldnt yyou use a block size being an arbitrary width that all units are a factor of? In that case, couldnt you just have a 'size' value on the objects and check for nearby blocks depending on the objects size when comparing collision?

[DrEvil]

If you take your 2d grid, and add a field to each cell that is simply a number. You can probably get by with an 8 bit number of less depending on how many variations in size your units are. Scan all the cells, mark any cells bordering an obstruction with the value 0, go through again, any cells bordering a 0 mark as 1, then again and mark borders of 1 a 2 and so on until all cells have a value. You end up with each cell marked with the distance from an obstruction, so for large units you can pathfind only on the >= 2 or whatever. Pretty simple, though you have to update the values when buildings are placed or destroyed to keep the values up to date.

[Captain P]

This would simply be a matter of rejecting all cells not just when they're solid, but also when certain other cells around them are solid. That is, a 1x1 unit always fits in an open cell. A 2x2 unit sticks out of a cell, and therefor also occupies on cell to the right, one below and one right-below (when taking the upper-left part as the units center). Then, every open cell whose right, bottom and bottom-right neighbor are also open, can be moved to.

You can perform this check when doing the path-finding, but it's likely more efficient to generate a map for each unit size. Depends on whether you're speed or memory constrained.