AI remembering obstacles without a grid

Question

For some research purpose I've build a small tanks game where you have 1 tank controlled by a player and one or more NPC tanks.

Now I want these NPC tanks to navigate through a field which they have no knowledge of. They can detect obstacles if they are in a certain range. If they detect those obstacles they should save them in a certain data construct that's easy to query. So that they can take them in account in pathfinding.

Now here is where I'm stuck : if my field would be a grid (level discretized in tiles) it would be quite easy for me, I would just save which tiles the obstacle is on.

But I haven't really worked with a grid, my tanks just move forward a few pixels depending on their speed, so a tank can be located on any pixel combination. Is this bad game design?

I could probably make a grid just for my obstacles, but that restricts a bit the kind of obstacles I can have.

Any suggestions/tips ? Please ask more information if needed, I was not really sure what to include.

Answer 1

The following is a 3D AI approach, but is easily translated to 2D (I dont know which you're using)

In our engine we have a dynamic path-node grid where a AI entity navigates through the node grid with A-star. When we then drop an object or is manually placing objects into the scene we update the path-nodes when there's a collision (not everytime its colliding but on enter or on exit) within the area.

So an octree or quadtree is recommended to speed things up. So Im driving my tank and the tank get's notified that it has been placed in another quadtree-node. Next we check all path-nodes which is also within the same (new) quadtree-node as the tank and we update the path-nodes however we want. If it was I tank I would set the path-nodes to a "Blocked" state and no other tank will be able to navigate through those nodes.

One important thing to note is that the path-nodes we're leaving must be reset, so we're not driving around and just blocking path-nodes, leaving a trail behind us.

If your not familiar with A-star. Here's one in 2D: http://xnatd.blogspot.se/2011/06/pathfinding-tutorial-part-1.html

Answer 2

Take a look at the Tiled Map Editor. Tiled is an open source tool for creating maps in a TMX (xml) format. Tiled is more frequently used (as the name suggests) for maps on a fixed tile grid, but it doesn't have to be. I'm discussing Tiled not to recommend a particular product, but to illustrate a concept. First, here's a little sample map I created using an object layer with a few polygons.

And here's an excerpt from the associated XML file that specifies the left polygon:

  <object x="335" y="285">
   <polygon points="0,0 322,9 236,156 -229,32 -252,-192 -166,-185 -84,-87 -49,-78"/>
  </object>

As you can see, this sort of approach doesn't restrict you to a fixed grid. If you create your maps using an editor like this, you'll need to read and parse the maps into your application. So, for example, you might have a polygon object, that takes the data from the polygon--the various points--and loads it into your scene.

I think you'll find that whatever approach you use to store your map for navigation purposes, it's worthwhile to use the same approach to store the map in the tank "ai".

In other words, if your map loads a series of polygons, lines, etc., you can have each tank maintain its own representation of the map--essentially, a subset of the map used to generate the level. This way, when a tank "learns" about a particular object, say a polygon, you don't have to recreate or reform the polygon under some separate data structure, you simply add that polygon object to the tank's "knows about" collection.