I`m currently thinking of different kind of path finding alg. for RTS type game.

Some specs:

Game has actors from size of 20cm*20cm (drone) to size of 15m*8m vehicles.
Game is located in city enviroment.
Enviroment is builded from blocks of size 10m*10m
There are some fence/wall props that can be placed freely. (don`t follow grip)
Blocks can be changed dynamicaly to destroyed versions. (destroyed bridge is impassable)
Map is not fully 2d (there are bridges & multible street levels layered)


And while I was thinking Idea came to my head. (Thats rare :D )
Could summed area table used to fastly check if given area is free for movement?

I dont have pseudo code yet, but it`s easy to think
in head of area conquering algo based on SAT.

Benefits of SAT:
Size of rect that is scanned is free.
Computing time for one check is allways O(1).
Easy to generate.
Recursive path fitting is supported.

Now I`m wondering is there any docs/pdf/research
done on using SAT on pathfinding?
And can you see broblems with SAT pathfinding?

/Tyrian

Could you describe your idea of how SAT would work here? I'm not sure I follow yet, but that doesn't mean it shouldn't work :-)

I'm not aware of research yet either, but since I don't quite understand your solution, it's hard to find similar papers!

Some refinment to idea. Conquering algo. is not good, but it can give idea of
what I`m thinking :) The final path construction is still open.
(First I try to get good conquering)



in image:
1. SAT can give answer to question: how much area is unmovable inside of this rect.
Rect can be of any shape, but it must be axis aligned, and it doesn`t tell where unmovable area is located inside of rect.

2. SAT finding, green is start and yellow is end. Gray is free terrain, Blue is building.

3. First rects.
4. Check rects and divide if not free. Remove if compleatly blocked.
5. Expand totaly free blocks.
6. Check rects and divide if not free. Remove if compleatly blocked.
7. Expand totaly free blocks.
8. Check rects and divide if not free. Remove if compleatly blocked.
9. Expand totaly free blocks.
10. Check rects and divide if not free. Remove if compleatly blocked. (Remove also unconnected)
11. Expand totaly free blocks.
...

Expansion blocks could be more agressive (stretched more to free direction)
Some sort of block combining is neaded, so that size of free patchway is known.

/Tyrian

It sounds like it could work, but it seems to assume you don't know the environment before hand. It's better suited to robotics rather than game AI.

I also guess it'd be very slow to run compared to A* on a known representation.

hmm... Yes, it would be better to do greedy depth first search.
Similar to A* heurestic, where travelled path and distance to endpoint
are taken as weight values. (distance to endpoint tells what is this paths
current best possible result)

Maybe checking rect that has one corner on current paths end, and opposite corner on end location. (Gives unmovable and movable area scalars whitch can be
used to calculate "possibily of free passage weight value", that can be used as
weight for searching)

Yes this is targeted on semi-dynamic enviroments.
(enviroment changes sometimes on some parts. (SAT neads little recalculation))
(totaly dynamic enviroment would be map where everything changes on each step,
and there would be little point on using any path finding :D )

About speed, each node/block can be checked on constant time,
so node checking is done in best speed there is.

Only thing left is to minimize checked nodes/blocks and if node size
can be size of free rect, then this could be realy fast.
And think that A* neads also to check more nodes than just optimal path :D

/Tyrian

[Edited by - TyrianFin on July 27, 2010 5:11:22 AM]

I kinda like the idea, but for purposes other than run-time pathfinding. From what you've described it seems you would have to generate every rectangle of the "tree" for every path query. When it's unlikely to change all that much during run time (Even with dynamic worlds). Theres also a lot of wasted computation compared to an A* search, it resembles the results you'd expect from Djikstra's algorithm. Of course you could always cache the result and perform A* queries on the resulting grid-like structure.

What I think this idea could be best suited for is some offline processing of a level to generate a nav-mesh representation. Similar to how Recast Navigation uses voxels to generate it's own nav-mesh output.