Region search - Algorithm explanation
First, lets take an example map:
Ugly, huh? Yellow areas represent wall.
Then the key idea. Divide the map in several regions. In this case, lets make 17 regions (more than 50 regions are recommended for complex 256x256 map):
One color represents one region.
The most important thing to remember when doing regions: you must be able
to access from all region points to other that region's points without
'visiting' other region. In other words each of the regions must be unbroken,
in one piece, intact.
Looking at the picture should give you the idea.
For better pathfinding just make more regions.
Drawing regions manually is boring and time-waisting so you should do a program that divides maps into regions. How to do this:
- Select one empty point from map and create a node there
- Look at empty areas next to that node (up,down,left,right,up-left, etc.). If empty spot is found, create a new node there. Do this to all empty places next to the first node.
- Destroy the first node and fill it's place with 'region x' color. Add 1 to 'filled'-counter.
- Create new nodes next to new nodes we now have.
- Destroy the older nodes and add 'filled'-counter depending on how many nodes you destroyed.
- Repeat 4 and 5 after 'filled'-counter reaches for example 250.
Now you have one region that has 250 nodes/map blocks in it. Then select one point from that region's border. Now fill another region (250 size) here. Then select a new point from that region's border and start filling. Repeat until an 'dead-end'. Then select randomly new empty (not any region, not wall) point from map and start filling from there. It's important to use some sort of fill function to make your regions intact.
This is not the best system for making regions, I know, but you can make your own routines for regioning. If you have clever ideas how to do the regioning, please contact me.
So what to do with the regions?
Look at this picture:
"arrow
map"
This is a 10x10 arrow map. Yellow blocks represet wall again.
'S' is the goal where you are heading.
Now when you look at the map above, you can see that after you have calculated
all the arrows to the map, you can go to 'S' from anywhere just by following
the arrows. This is really really fast, you need only read memory once
to move towards the goal!
Then how to calculate those arrows? Just place a node to 'S' and create new nodes around it. Their direction is to where they came ('S' at this point). Create new nodes around older and set their target also to where their 'parent' was. Repeat this for a while and you will get the picture above! This should be trivial if you have done A* or Dijkstra before.
If you want to add swamp, forests or roads, just put a timer for each node you create. If you create a node to swamp, put 10 to timer, to forest 8, to plain 3 and to road 2. Then just wait until timer tells you when to move that node. That will make nodes move slower on swamp than on road. This is also the same system as in A* and Dijkstra.
Back to the Region search:
You could make arrow maps for every single empty block in your
map. This would be truely optimal route and REALLY fast but it would take
n^2 memory, n being the size of your map. (256*256)^2 = 4 gigabytes! You
don't have that much memory, do you? That's why we have these regions.
You use arrow maps to make you units move to the border of region you
clicked and then just seek the actual goal point.
To create a path from anywhere on the map to region number 1, just place nodes _at the border_ of that region. Then create the route-map (=arrows). It will be same size as your orginal map. Now when you want to move your unit and you click on the region number 1, you can just follow the precalculated arrows to reach the border of the region nr.1.
Do these arrow maps for each region and then you can go from any point to any region's border using the optimal path. After reaching the region's border, just use robust search or some other stupid but fast algorith to reach the target point. Remember that now you only have to move _inside_ the region for about 10 blocks or so (depending on the size of your regions). If you use A* to make your unit move inside the region (to reach the actual goal), make nodes only inside the region you are in.
If you move your units inside one region you don't benefit anything from your arrow-maps and regions. But in that case the route is so short it takes ~0 time to search the route.
Hope you got the basic idea of Region search but it'll need much optimizing for:
- memory usage (you probably don't want to use 256*256*200=13 megs for pathfinding)
- better route (think about reaching the border of a region.. there are some problems)
- dynamic parts