4 ms·
> Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal path
by vanderZwan 12y ago
> Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A shown here.*
Another example is when you are dealing with large crowds. Vector fields tend to shine there. A simple example is using a vector field when dealing with a large swarm with one goal:
http://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007 http://gamedevelopment.tutsplus.com/tutorials/understanding-...
Something more slightly more advanced yet incredibly powerful would be "continuum crowds", where the agents in the swarm are also obstacles for each other, affecting the vector field:
https://www.youtube.com/watch?v=lGOvYyJ6r1c https://www.youtube.com/watch?v=lGOvYyJ6r1c
http://grail.cs.washington.edu/projects/crowd-flows/ http://grail.cs.washington.edu/projects/crowd-flows/
The intriguing part here is that these potential field can have any source - so it's relatively easy to get complex behaviour, such as pedestrians avoiding cars, or prey/predator behaviour.
Again, these are more relavant with large crowds, so as stated before: the best approach all depends on the particular use-case.
- gavanwoolery 12y agoThat is an interesting example with the fluid pathfinder - had not considered a fluid solver for that application but it seems to work really well - even perhaps mimicking nature. If you look at a large flock of Starlings their movement is almost fluid-like: http://www.youtube.com/watch?v=XH-groCeKbE http://www.youtube.com/watch?v=XH-groCeKbE
- raymondh 12y agoThanks for that link. It was a marvel and a delight.
- amitp 12y agoA* is typically for single source, single destination. For crowds, if you have lots of agents that want to go to a single destination, you can often use Breadth First Search or Dijkstra's Algorithm. That tutsplus article uses Breadth First Search. The crowd flow research is neat. The videos are especially fun to watch. http://gamma.cs.unc.edu/research/crowds/ http://gamma.cs.unc.edu/research/crowds/ is another nice set of papers.
- lenocinor 12y agoYeah, vector fields are great for big crowds. Hitman: Absolution, which has one of the best implementations I've seen for crowds, uses them: http://twvideo01.ubm-us.net/o1/vault/gdc2012/slides/Programming%20Track/Fauerby_Kasper_CrowdsInHitman.pdf http://twvideo01.ubm-us.net/o1/vault/gdc2012/slides/Programm...