Should I share the same tile structure for display and pathfinding?

I know how to display a 2D map with tiles.

I know how to make a pathfinding algorithm using A*.

Those two things demand a structure or a class. My question is : do you use the same structure for displaying and path-computing ? Node structure for pathfinding demand to add some data : x position, y position, F, G, H plus the Parent Node. Tile structure for displaying can be optimized to almost only one information : the value of the tile.

Do you use a big class for your tiles, that handle both displaying and pathfinding, or do you use a different method ? Thank you for your advices !

• Awesome question, I really needed to learn this but I didn't know what to ask. Commented Oct 7, 2010 at 18:41

My question is : do you use the same structure for displaying and path-computing ?

No, I don't. You can get some optimisation out of calculating your A* directly onto the tile-map, but then you can't easily use your A* algorithm for things that don't map directly to the tiles. Also, it means you can't run the A* algorithm simultaneously in multiple threads as they end up sharing the map data. Finally, certain methods of moving don't allow the tile=node optimisation; a vehicle that needs space to turn around could potentially arrive at the same tile from different directions and have different options in each case - they can't be merged into one score.

So I suggest keeping the data separate.

• While it's interesting to keep them separate, you don't need to use an explicit graph for path-finding, you could have a "tilemap" with just the collision/cost information, totally separate from rendering and from the logical model. For example, if you add an object to the world that is not stored in the tilemap, but just using (x,y) coords you could still put it in the collision map and use that for grid-based path-finding. Commented Feb 21, 2012 at 18:15

From a software development perspective, it's always good to keep different things separate.

For a quick and dirty solution, put everything together and start working on game specifics.

For an extendable solution, keep things apart: you don't want to be changing tile classes because your pathfinding algorithm got changed! Keep two structures: one representing visible game tiles and one representing the pathfinding structure. Ideally, a pathfinding algorithm is kept low level, so maybe an array of x,y points as input to the algorithm is a better idea than to provide it with your tile classes. The algorithm itself can setup arrays for F,G,H values.

I think in this case (and I assume that you strive to be a good programmer), you should go for the extendable solution, because it won't take you that much extra effort but it keeps your code cleaner and you will gain good practice experience.

I was once building a tilebased game on the Amiga 500 with 512x512 tiles but the player could only move 8 tiles, so I generated a "9x9" tiles "wall map" pr. soldier. If I had done this with the original map, I would first of all have had to "clear it up" after each calculation + the amount of memory needed to have both tile data + pathfinding data would make 512x512 become a much begger memory hog.

So no, keep things as small as possible and seperate so you can tweak them pr. object/class if needed. Another thing to think of might also be that some of your moving objects MIGHT move differently over certain parts of the map. Eg. slow in sand, can/cannot swim, can open doors etc.