I have an application where, given a grid, I want to find a path from A to B that is deliberately inaccurate, to a variable degree. The only constraints are that a path must be found (which will always be possible, due to it being on a square grid of interconnected nodes), there must be a random factor (so that the user can press ''refresh'' and potentially get a different path) and that the user can somehow alter the degree of inaccuracy. Efficiency is not a concern as the grid will not be more than about 20x20 and the application is not hard real-time. Any ideas? [ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Just off the top of my head: Use A* and vary the edge weights before each search.



ai-junkie.com

hmmm.... one solution would be to take a random sample of a certain number of points from the grid. Then rather than searching over the grid space for a path, you search over the points. ie how can you get from the start to the goal, going through the points chosen, in the shortest distance. The more points you sample the closer it will be to optimal, the fewer the more random it will appear. A picture would really help if my explination isn''t clear, I think i''ll try and find one.

a genetic algorithm whih is stipped before it converges could do the trick too...

--Spencer

"Relax, this dragon is sleeping..."

quote: Original post by Kylotan
I have an application where, given a grid, I want to find a path from A to B that is deliberately inaccurate, to a variable degree. The only constraints are that a path must be found (which will always be possible, due to it being on a square grid of interconnected nodes), there must be a random factor (so that the user can press ''refresh'' and potentially get a different path) and that the user can somehow alter the degree of inaccuracy. Efficiency is not a concern as the grid will not be more than about 20x20 and the application is not hard real-time.

I would suggest implementing a version of the Steering Behaviors and just alter the influence of the attraction force to the goal, as needed. It would be a dynamic, and computationally low impact solution, that would as a side benefit, really look like wandering. I know, I''ve done it before to produce a wandering NPC.

Eric

Not a very elegant approach, but it may do the trick :

1. Find the optimal path with whatever algorithm you want.
2. Choose some navigation points accross the path previously found.
3. Move these nav points randomly. (you may need to make sure there is a path between the orignal position and the "randomed" one).
4. Compute the paths between each nav points.
5. Concatenate the paths from (4) to obtain a suboptimal path.

"I would suggest implementing a version of the Steering Behaviors and just alter the influence of the attraction force to the goal, as needed. It would be a dynamic, and computationally low impact solution, that would as a side benefit, really look like wandering. I know, I''ve done it before to produce a wandering NPC"

Depending on the environment that will not guarantee that the agent finds the goal Geta. Kylotan stated that the goal must be found.



ai-junkie.com

quote: Original post by fup
Just off the top of my head: Use A* and vary the edge weights before each search.



ai-junkie.com

I think that would give the best results. Most of the other suggestions might end up with paths going around the map 5 or 6 times, buy simply weighting nodes randomly from 1-X (where x is set by the user to control the randomness) and using that in A* would result in a slightly random path, but it will generally still find a good path. I''ve done something simmilar before and it worked fairly well.

I third the random wieghting/shortest path method

George D. Filiotis

I am a signature virus. Please add me to your signature so that I may multiply.

I agree that the a* random weighting will give a non optimal path, but the amout of wandering might varyy greatly, so a more algorithmic approach to altring the weights would probably work more in your favour, depending on how much wandering you want. But you have to be careful. If the grid is sizable, then the a* might end up searching all the nodes to find what it thinks is a decent path, and to be honest, searching all nodes, regardless of the algorithm is slow and something that you shoudl avoid at all costs.