Pathfinding just like those clever humans..

This paper discusses the use of empirical cost-surfaces derived from substantial amounts of player-traced movements in Darkwind, for the purposes of improving A* pathfinding by AI vehicles. My core ideas are that (i) there are a number of subtle factors related to both effectiveness and aesthetic value, which definine optimal routes around the terrains, and that (ii) it may not be feasible to deal with these factors algorithmically. I aim to achieve efficient, believable (‘human-like’) routes which navigate terrain features and surface types sensibly, are safe from collision damage and, where possible, enemy fire.

Since Darkwind is a well established online multiplayer game, it provides substantial amounts of empirical evidence about player-chosen routes. The basic premise is that we have thousands of player-controlled cars travelling aorund the maps every week, so why not let the computer learn the favourite routes taken by humans?

Draft Paper here (pdf, ~3.5MB)

This is all based on ‘votes’ that I have been gathering in the game for the past 12 months or so.

pheromone trails

You can leave a response, or trackback from your own site.