• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# simple pathfinding

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.

21 replies to this topic

### #21BeanDog  Members

Posted 01 June 2000 - 06:17 AM

OK, I think I get the idea of the region search. Only problem is, what happens when the path from one region to another is totally blocked by dynamic units?

Also, how would you calculate the arrow paths from each region to the surrounding ones if the regions aren''t convex?

Hey! I''ve got an idea. If your map is divided into regions, you only have to store the paths to each of the SURROUNDING regions, and store the paths (in regions) for the farther paths. That way, you would have to do maybe 3 memory checks (oh darn) per iteration, but you wouldn''t have to store all 500 values for arrows, just, say, 15. that would be 256x256x15, or less than a meg, plus a little for the paths to each region, 500x500 array (for the next region to go to from one region traveling to the destination region). You get my vision?

~BenDilts( void );

### #22Chance  Members

Posted 02 June 2000 - 05:01 PM

One way to do it would be to compute paths around obstacles as lines. Then store all the lines in a structure that has waypoints (points along the line) and connections to other lines. Then, to make something move anywhere in your world tell it to move along the lines. Doing it for all obstacles may be a bit excessive so my suggestion would be to compute the lines only around objects of a given (larger) size and use another solution for actually reaching the waypoints, because there may be a small obstacle between the thing you want to move and the nearest way-point.

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.