Some time ago I got and idea on pathfinding. This is not really OpenGL-related but I guess it’s not needed here right?
Well, I have two problems:
1- I don’t have a reference. It would be great to test it against an improved hierarchical A*, which I think is actually the best.
2- I don’t know how to generate test cases. I would actually target 2D cases but how to generate those maps?
For (2) I actually did some testing “by hand” and it was tedius work. It also took over 4 days per-test so I realize it’s really too much to get away with.
Another problem is that I think I can expand it to account for “move cost”, although I’m not sure. Do you think this would be a nice functionality?
Do you want to test the algorithm in terms of correctness or finding a good (best) solution? Then I would implement a simplified version to make it easier to construct testcases, something like searching in a bitmap or a vector graphic. Then you can make a testcase in paint.
Also it’s easier to compare against other algorithms, because you can write your algorithm in a way that takes the same input as the demo application of the other algorithm.
Do you want to test the algorithm in terms of speed? Then you’re better of with a complexity analysis than with actual testing.
Do you want to test the actual implementation of the algorithm for speed? That’s the hardest part, since you can’t simplify anything and you need really large testcases. You most likely need to write a program that generates testcases, for example by repeating patterns or generating random maps. Search the web for maze generation algorithms, they may help too.
Expanding an algorithm to include move cost is very useful for most applications. Just imagine a game with different terrain types that give different movement speeds. A related thing would be a cost for turning (you have to move slower when making a sharp turn).
Thank you for your reply Overmind, you are effectively touching many things I shall consider.
Originally posted by Overmind: Do you want to test the algorithm in terms of correctness or finding a good (best) solution?
The algorithm itself is very simple. I’ve already made some test cases by hand and I already know when it goes wrong.
As for the optimal solution, I’m quite sure it will be “optimal enough”, altough I’m not sure it’ll be “the best”. I would like to test it to check this out. As for the non-working cases, I’ll work on them later.
Originally posted by Overmind: Do you want to test the algorithm in terms of speed? Then you’re better of with a complexity analysis than with actual testing.
I personally never liked this because it misses a quite good amount of informations such as the O-constant and the ‘l’ from which the O kicks really in.
Altough I realize it’s quite good for theorical reasons, I won’t apply it. Another reason is that it would not make a compare since the algorithm is optimized for my own data representations.
Not to mention the fact there’s no good reason to measure the best or worst case.
In a best case, the algo is a NOP.
In the worst case, the running time depends on the data evaluated but this implies there’s no free space to “walk in” so the hypotesis is unrealistic.
Originally posted by Overmind: You most likely need to write a program that generates testcases, for example by repeating patterns or generating random maps. Search the web for maze generation algorithms, they may help too.
That’s exactly what I was meaning to do. I was not only going to use maze generation but also something based on perlin noise, something like generating a noisy mask. I’ll probably blend the two things togheter.
Originally posted by Overmind: Expanding an algorithm to include move cost is very useful for most applications. Just imagine a game with different terrain types that give different movement speeds.
I have some ideas to make this work but I’m not sure. Added anyway on my TODO list.
Originally posted by Overmind: A related thing would be a cost for turning (you have to move slower when making a sharp turn).
Also added this but I have no idea how to implement the feature. The “cost of turn” is quite a difficult concept. Shall I use a LUT? A function? On your experience, how much this feature is requested? Putting it in-core would probably make it quite slower but I may consider a post-processing thing or a branch with turning cost.
Obli,
it seems some of your questions can’t be answered without a context.
F.ex. the “turning cost” can for a slow-moving RTS be dependent on unit-type, for a racing game it’s likely dependent on at least traction + speed + corner-radius + weight of vehicle, for a Quake-style game it could be anything from instantaneous to very expensive (think of running on ice close to a wall with a 90 degree outer turn) in terms of time required to slow down, turn and then accelerate.
OK, I’m expanding the scope here from a simple optimized path finder (shortest route) to include physics, but most games nowadays I know of include physics even at this level to some degree or another.
Basically, finding the shortest route might not be what you want if you’re interested in the fastest route for a particular kind of moving object. For some scenarios there could be a very large difference.
You’re right in telling me I shall considering the context. I am just starting it so I’m not sure about its usage (provided it really turns out correct and competitive against other algos).
Originally posted by tamlin: OK, I’m expanding the scope here from a simple optimized path finder (shortest route) to include physics, but most games nowadays I know of include physics even at this level to some degree or another.
Reading your post I realized I shall really consider this. For the time being, I’ll just do “Short enough path”, I’ll expand it later.
This may also cut it for some applications. Other metrics will be added later in derived algorithms.
Originally posted by tamlin: Basically, finding the shortest route might not be what you want if you’re interested in the fastest route for a particular kind of moving object. For some scenarios there could be a very large difference.
In case I can do this, I think I’ll use a LUT to evaluate the turning cost. Since LUTs are used for generic stuff, maybe I could think about “generic metrics” such as for example, “path safety” and such.
I must say however, all this is getting very complicated. I’ll try to get it running simple and then build on it.
Thank you anyway for your posts, they turned out to be pretty useful to clear up my mind.