Region search - The worlds fastest & best pathfinding algorithm
|
Update 2. April 2004 While this method of path finding isn't very useful in dynamic environments, such as most environments are, I believe that precalculated routes to various goal nodes (or goal areas) can provide a useful heuristic for search algorithms such as A*. This method will notice new blockages and try to find a way around them, but the paths generated by it will not use any newly created shotcuts. So the precalculated costs should be calculated on a map which has all the doors open and all breakable walls broken, and won't work on more dynamic environments where the amount of search nodes increases over time. I have yet to do any proper research on the subject but this paragraph should be enough to give you the idea. So bear in mind that the following stuff is OLD, pretty non-useful and verbose. |
You don't believe me?
Well, here's some comparsion between popular pathfinding algorithms:
| Search algorithm | Evaluation time (* | Allows 'heights' (** |
|---|---|---|
| Region search (99% close to optimal route) | 3 | Yes |
| Robust Search (poor route) | 15 | No |
| Best first (ok route, used probably in c&c) | 300 | No |
| A* (best route, used in turn-based strategy games) | lots more! | Yes |
(* estimate for a test map, smaller means faster
(** meaning that swamps are slow, roads are fast
Some key features of Region search:
- can solve any maze and very complex map and it's 99% close to optimal path. No one notices the missing 1% ;)
- allows maps to be dynamic but gets slower depending on the amount of dynamic parts (blown bridges, buildings).
- it can be used in 3d pathfinding also, if you use some sort of route points and some brains.
- time to goal: almost O(n). n is the optimal lenght to the end! You need to read 1 byte from memory to make your unit move 1 step closer to goal (using optimal path).
- if you make a C&C-game your units will take best use of roads and they will avoid swamps, forests and other slow-moving places
Something bad also, but only small things:
- depending on how good you want Region search to be and how big is your map, it will eat lots of memory. For example: 256x256 tile map with quite good Region search takes 5 megabytes of memory. But almost zero memory for individual units! Meaning that you don't have to save each unit's path to memory like in other algorithms. So you can have like, thousands of units, and their pathfinding is fast and costs no extra memory. Even though, I admit 5 megs (or much more) is quite a bit for routefinding.
- Region search is not that dynamic you could use dynamic influence maps, but no one uses them today anyway ;)
- Some problems with dynamicy. Blown bridges work great (in algorithm, not in real life ;) but complex bases may have some problems. I suggest you to make buildings so that units can go around them, i.e. make enough room for moving around each building (it's that way in real life too). Or you can use A* inside bases and Region search outside bases. Read on to know more.
Okay now that you've read the hype, you must be hungry for an at-least-100x-faster
pathfinder 