Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Kai_Kratz]

After reading and watching the forums for the last 12 or so months i finaly came across something i found worthwile enough to post yet even create a forum account ;)

Following this link you find a realtively new research paper about a pathing algorithm called "Corridor Map Method" dating early 2007.

http://people.cs.uu.nl/roland/motion_planning/cmm2.html

To give you an idea why i brought this up, one example from the given link:

The picture below gives an impression of 5000 paths, each traversed by a character having its own long term goal. All characters avoid each other in real time. The cpu-load of this simulation was 40%.

Cheers!
-Kai

[Random832]

After reading and watching the forums for the last 12 or so months i finaly came across something i found worthwile enough to post yet even create a forum account

Following this link you find a realtively new research paper about a pathing algorithm called "Corridor Map Method" dating early 2007.

http://people.cs.uu.nl/roland/motion_planning/cmm2.html

To give you an idea why i brought this up, one example from the given link:

The picture below gives an impression of 5000 paths, each traversed by a character having its own long term goal. All characters avoid each other in real time. The cpu-load of this simulation was 40%.

The CPU load is meaningless - that just means it's doing things more slowly than it could have. What is important is how long it actually took (in terms of cpu cycles)

[darius]

From what I saw in discussions about path finding before I think this would not be of any use as it is an algorithm that computes static path map, than uses it. But in DF there is nothing static. Although there could be some sort of hybrid implementation. Precomputed map and if anything happens to change map area around it is invalidated (pushed to be recomputed). Also another thing that DF has discreet map whereas this algo (I think) uses real valued map.

[Mel_Vixen]

McKenna	Fictional city

Looks like 1000 chars take ~7.5 % this would equal to ~10 FPS if we use 75% CPUtime for pathing and the 25% for everything else. The problem is that it looks like as this pathing only uses 1 Z level. [edit:] on the used 2.4 GHz core.


On the pro is that this 2 Citys are 1600*1600 and 4000*4000 which is much bigger then our average DF map if 1 Pixel equals 1 tile. Also we normaly dont have 1000 creatures on one Map. most maps would be between 100 and 500 (Dwarfs Goblins etc + animals). A 6*6 Embark map with 30 Z levels would still have less tiles then a singletile Z level 1600*1600 Map but this doesnt mean much.


A testimplemention of this algorithm for a Tile map with multiple Z level would be needed to get how efficient and flexible this alghorithm is.

[Kai_Kratz]

Hello everyone,

nice to see some people took a look at it

From what I saw in discussions about path finding before I think this would not be of any use as it is an algorithm that computes static path map, than uses it. But in DF there is nothing static. Although there could be some sort of hybrid implementation. Precomputed map and if anything happens to change map area around it is invalidated (pushed to be recomputed). Also another thing that DF has discreet map whereas this algo (I think) uses real valued map.

I was well aware of these 2 points before posting.
As you already suggested recomputing can be done, and it is not that expensive. It can be archived by using the graphics cards Z-Buffer to create the Voroni-Regions neccesary to set up the corridor map.

As far as i understood the paper the algorithm is also working in a discretized enviroment.

This animated gif shows a sample from a 3D eviroment.


Cheers
-Kai

[Mel_Vixen]

Hmmm just looked throught the paer myself and i might have found a problem. Small Maps (2*2 embark and smaller) could get slower because they get a relativ overpopulation and to small corridors.

As you see in the Cpu-load Diagram the performence of the smaller city McKenna decreased after a population of ~7500 was reached. As said before DF maps are normaly smaller and have less space between obstacles so higher pops might cause a performance decrease.