• Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

# Pathfinding/A* with variable Unit Size in RTS

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1TMGeorge  Members   -  Reputation: 127

Like
0Likes
Like

Posted 18 October 2008 - 01:46 PM

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

### #2Crazyfool  Members   -  Reputation: 307

Like
0Likes
Like

Posted 18 October 2008 - 03:27 PM

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?

### #3DrEvil  Members   -  Reputation: 861

Like
0Likes
Like

Posted 18 October 2008 - 04:28 PM

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.

### #4Captain P  Members   -  Reputation: 1084

Like
0Likes
Like

Posted 19 October 2008 - 12:33 AM

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.