Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 !

share|improve this question
    
Awesome question, I really needed to learn this but I didn't know what to ask. –  DFectuoso Oct 7 '10 at 18:41
add comment

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  Trinidad Feb 21 '12 at 18:15
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.