Archived

This topic is now archived and is closed to further replies.

Pathfinding in Isometric/RTS

This topic is 6266 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I am developing an RTS and I am heavy into the unit pathfinding. I have overlayed a grid on my tiles and I run an A* algorithm to find a path through the graph. Basically, the unit moves to the center of each tile until it reaches the goal tile. This works great for single units. I have no problems with understanding A* or shortest path algorithms, but I''m having trouble when I try to scale unit movement up to many units. I thought I would try to work out some of it on here and see if anybody has suggestions. I want it to be robust so each unit can have a variable width/radius, but how do I incorporate this infomation into the A* algorithm? Right now I have a unit list associated with each cell/tile. So, I can test if a cell is occupied and not include that cell in the search. This isn''t too bad and does avoid some collisions, but since my units can have different widths this fails badly when the unit is at the corner of a cell for example and has a width about equal the cell width. In this case the unit is actually partly in 4 different cells. As a consequence of this, if I let my units be larger than a quarter of the cell width, they bump into each other all the time using this method. I mean I could just exclude all cells that have any part of another unit in them, but this looks stupid as well because the moving unit will go way out of it''s way sometimes to avoid a little unit that is just touching a cell. Does this make sense? The pathfinding is working well for the static map, but not for other units on the map (even if they aren''t moving). One thing I tried is to just leave the A* as a global and rough search, and then resolve the collisions locally by tracing around the unit. This works, but it looks stupid because there are so many collisions. It takes forever for a unit to sift through a large group of units when it has to resolve each collision with tracing. I really need a way to prevent the majority of collisions from happening in the first place and then I can just resolve the few collisions that may happen because of other units moving out of place and such. I have given it a lot of thought, but I can''t find any reasonably simple solutions (if there are any). Games like Starcraft really handle this elegantly. I have a greater respect for pathfinding and why so few games get it right. To produce elegant movement of variable size units through an isometric map is not easy. Does anybody have suggestions or good articles? I have looked at the gamasutra articles, but they really don''t go into specifics. I would like to hear from anybody who has gone through this kind of problem. Thanks, Abs

1. 1
Rutin
39
2. 2
3. 3
4. 4
5. 5

• 14
• 18
• 12
• 14
• 9
• Forum Statistics

• Total Topics
633360
• Total Posts
3011516
• Who's Online (See full list)

There are no registered users currently online

×