Advertisement

AI in a tile based game.

Started by August 25, 2009 02:17 AM
1 comment, last by Waterwalker 15 years, 3 months ago
In a tile based game, I am given the players X and Y positions on the grid, I need to figure out how many steps the NPC needs to make and in which direction on the grid to get to the player. However, there are objects in the way, the NPC may not even be able to get to the player. How can I develop AI that will efficiently find the quickest way to reach the player(how many steps and in which direction on the grid). I was wondering if anyone can direct me to an article or explain it to me.
http://www.policyalmanac.org/games/aStarTutorial.htm

Should be easy enough in 2d tile based (each tile being a node).

Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.

Advertisement
This is a classical "find shortest path in a graph" problem which should yield tons of results when googling. Nanoha already pointed you to one algorithm to solve this common problem, the so called A* (a-star). This is an enhanced version of the most famous algorithm invented by Dijkstra. Those buzz words should help you find more results throughout the web.

Basically all those algorithms boil down to creating a graph from your walkable area. In your case its straight forward since each cell center would be a node in this graph connected by edges marking the walkable connections between the cell centers. Each edge is associated with a cost (usually the distance it takes to get to the adjacent node). Then you use those well described algorithms to find a shortest path in this graph.
------------------------------------I always enjoy being rated up by you ...

This topic is closed to new replies.

Advertisement