Optimizing A* for grid maps

Re:Optimizing A* for grid maps by darylteo on Sunday February 22, 2015 @05:50AM (#9089010)

I attempted the recent MIT AI competition, but stumbled at the point where I wanted to build something like the post suggests, except that the map is not initially discovered. :( if anyone could point me to a method for constructing such a graph through discovery, that would be great.

[ Parent | on HN ]

Re:Optimizing A* for grid maps by sgift on Sunday February 22, 2015 @07:37AM (#9089180)

Not a solution but a starting point: http://en.wikipedia.org/wiki/D*

I used this for a similar problem in my computer science studies. We had a map with an unknown layout of fields, each with a different travel cost and had to drive a tour of multiple flags in the fastest way possible. It worked quite well.

[ Parent | on HN ]

Re:Optimizing A* for grid maps by komaromy on Sunday February 22, 2015 @10:18AM (#9089648)

A*-like algorithms aren't really even applicable to Battlecode though because of the tiny bytecode limit. You're essentially forced to use local navigation or something like distributed BFS.

[ Parent | on HN ]