Author Topic: jKilavuz: a guide in the polygon soup  (Read 21659 times)

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: jKilavuz: a guide in the polygon soup
« Reply #30 on: March 09, 2008, 12:08:25 pm »
the PacMan levels are flat and grid so you dont need jKilavuz for it IMHO. but you can use jKilavuz's A* implementation for sure

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: jKilavuz: a guide in the polygon soup
« Reply #31 on: March 26, 2011, 12:55:33 pm »
A few years ago I studied for cooperative pathfinding and implemented a prototype based on David Silver's academic paper. It's called WHCA* (Windowed Hierarchical Cooperative AStar). My implementation was incomplete and far from perfect but functional. Yesterday my Google alert notified me about a post which is asking for sample code for cooperative pathfinding. I've published it here as it is http://www.jkilavuz.com/whca/, hoping it may help someone.

Seems as David's original paper is not where it should be, but there are many copies on the web. I had included my copy in my page. There is also a youtube video showing demo running.

A couple of notes (if I remember correctly)
* "Normal" A* can tell you if there is no solution but WHCA* cannot (at least as it is)
* With normal A* you get unnatural and unaesthetic paths unless you do some post processing. Same applies for WHCA*.
* The degree of cooperation depends on depth (of time) of search. If two units are blocked in a narrow corridor of X units of length, search depth should be at least X+1 to solve this situation.
* As expected there is a trade off here: The deeper the search the more likely it should solve blockages but the more expensive it will be.
* As the name suggests, the search for each unit is windowed. Each unit searches for a partial route to its destination at regular intervals. This sometimes results in -seemingly unnecessary- waits.

r a f t