# AI remembering obstacles without a grid

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.

• how big is each map? Dec 22, 2012 at 16:31
• so you're asking about 2D collision detection, but more advanced than simple grid field comparison? there are lots of techniques to to this and a lot of possible optimization, but you could start by saving [x/y pixel position + approximate radius, or x/y rectangle size or any other simple geometric form ] per tank and per obstacle, and always compare the distances from each objects outer radius Dec 22, 2012 at 17:08
• @JoséIgnacio The maps are 700x600. But that doesn't really matter, since it is conceptually. I should be able to use the techniques in much larger maps too. Dec 22, 2012 at 17:12
• @cppanda I'm not actually asking about the collision detection, that's all in place. I'm asking if it's possible without a grid to remember obstacles and do pathfinding later on. Dec 22, 2012 at 17:16
• If your map is storing data of objects that aren't in a grid "tile" structure, you already have a data model for how your tanks can store this data, no? Feb 20, 2013 at 22:39

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

• Well It's 2D. And the obstacles one tank found, should not be propagated to any other tanks. I don't understand the octree/quadtree's though. Dec 22, 2012 at 19:10
• Well octree or quadtree is just a way to take your world and split it up in zones. Octree have a zone structure like this: cedricthieulot.net/images/douar/octree.png and a quadtree have a structure like this: cs.sandia.gov/~kddevin/LB/figs/quadtree.gif. So a quadtree would fit your needs! Use rectangles to check if object rectangles are contained within the a zone and add that object to a zone objectlist. There's some more rules to take into acount. But Im sure there's some great tutorials out there Dec 22, 2012 at 19:21

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.