• Advertisement
Sign in to follow this  

Excluding vertices from polygonal roadmap - for pathfinding

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been playing with pathfinding using A* using a polygonal map. (One bounding polygon with polygonal obstacles)

For this I created a roadmap, connecting all reflex vertices with each other if they had visibility using an r*n*log(n) angular scan algorithm (n*log(n) per reflex vertex)

Then I discovered that not all of these reflex-reflex lines are actually needed. Consider the edge r1-r2 line, if r1 has visibility of both sides of r2 (not necessarily the previous or next vertex) or vice versa, then the line would never be part of a shortest path (except of course the shortest path from r1 to r2 or from r2 to r1).

Quite a few reflex edges can be omitted this way, reducing the size of the roadmap.


I wonder if anyone else is doing this?


Example, all reflex edges are in red, but only the necessary interconnections have been added to the roadmap:

Edited by Polydone

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement