Hi guys, I am currently working on the path finding algorithm for a RTS game. The game mechanics allows a vehicle (which has the size of a full tile) to park between tiles, thus causing multiple tiles to be only partially occupied. Form a path finding point of view, is it better to treat a partially occupied tiles as fully occupied or subdivide the tile into small cells?
Thanks for your input!
My two pennies worth: From a path finding perspective, the only thing that matters is “is the tile traversable?” If a character can move on a tile half taken up by a vehicle then include it in the pathfinding. If it can’t then don’t. Where that will come into play would be the graphics though right? I would guess that someone on a open tile would look different from someone on a partially occupied tile. At least in the final, shiny product.
Again, that was just my thoughts. Really it depends on your game and how you want it to play out.
Subdivision is probably the better idea for this. Otherwise you’ll need to figure out a bunch of other “fun” things for it. Like what does partial coverage really mean with respect to a tile.
Doing multiple tile movement (Subdivision) might work better. Give an object a variable size and define the pathfinding map based on these sizes.
In my game, any vehicle can move onto partially occupied tiles as long as it passes the collision test. If I subdivide a tile into cells, say 4 x 4, I not only have to re-define the representation of a tile , also the search space could be 16 times bigger. I just don’t feel it is worth the trouble to incorporate this into path finding. Also it makes sense to avoid partially occupied tile in the search path (less chance of collision ). If the player deliberately want to move a vehicle onto a partially occupied tile, then a different path finding algorithm can be deployed when the vehicle is close enough to the destination.
This is why I don’t use tiles for path finding. I reference the tiles as points (the center of the tile is where the points lay over) and then apply the pathfinding with the points that touch the object are the starting points.