Pathfinding 2d java game further issues...

Question

Hi all. I asked a question some time ago on java 2d pathfinding... http://stackoverflow.com/questions/735523/pathfinding-2d-java-game

The game im developing is based on the idea of theme hospital. The chosen answer from my question, A* pathfinding, the link was awesome, and very helpful. I'm eventually getting to implement this into my game, however I have some further questions/issues regarding it.

In my game, the map will change. The tutorial assumes that the map is static (I think). I have been looking at the code, and as far as I can work out, I just need to create a method to call to update the game map in the pathfinding code.

Second, I see the class GameMap. I have my own class called Board which houses all the tiles. I believe I could integrate the methods on GameMap into my Board class. Right?

Third, I have been working on the reasoning that any rooms would be counted as blocked. I mean as in, any squares the room is covering are counted as blocked. I was thinking ahead to where the people will enter the rooms. They will then have to move around these rooms to get to various places. I was thinking I would just invert the Blocked boolean for each square, but this would not work for 2 reasons. 1, rooms could have ajoining walls, and potentially muck up pathfinding. 2, if the blocked status is simply inverted, then any solid items in the room would be seen as not solid when inverted back, which could cause problems when they are touching a wall.

Thinking about it, it would be better if you could make sides of a square blocked rather than actual whole squares. This must be possible, but I am just getting by using the tutorial in the previous question, and not sure if I should try and change A* to do this, or work on workarounds for the room items issue.

Any thoughts or suggestions on any of these issues? I'm implementing the simple path finding today, but just thinking ahead of myself.

Answer 1

If the game map changes you do need to recalculate paths, however you don't necessarily need to recalculate all paths depending on what changed.

You should integrate the methods of GameMap into your Board class (with modifications to the GameMap class).

To block sides of a square you could think of each tile as nine separate ones instead (3X3). For example for a tile with blocked horizontal walls, instead of a single square you can represent the tile (to your a* algorithm) as:

[X| |X]
[X| |X]
[X| |X]

A tile with a vertical and horizontal tile blocked:

[ | |X]
[ | |X]
[X|X|X]

You would have to store the additional edge information with your game map. Hope this helps.

Answer 2

From a quick look, it looks like the isValidLocation(mover,sx,sy,xp,yp) method defines if moving from point(sx,sy) to point(xp,yp) is a valid move.

If this method took into consideration the direction of the move, you could block specific directions out of / into a block without making the block entirely impenetrable. This way, you could have 2 accessible blocks next to each other with a solid boundary between them.

This approach has some interesting side-effects such as the ability to create one-way boundaries (block A has access to block B, but not vice versa.) Could be a useful game mechanic in letting the A* take one way doors (fire escapes?) into account.

There is an algorithm called Adaptive A* which can recalculate a portion of a path say, if someone stands in front of you. I would concentrate on the vanilla A* first, you could always calculate a new path from that point on if you found half way through that a previously valid path was blocked.

This looks like interesting reading: Real-Time Adaptive A* [PDF]

Answer 3

For the path question :

A simple solution is to recalculate the path if and only if the next move in the current path is considered as invalid (a new element has been put on the map, a new room has been added, a door has been moved...). Of course, you recalculate from the current position. The problem is more complex if the blocking element is another moving one. In this case, one of the two objet has to wait a few cycle, and the other has to re-path, depending on a priority. however, this may lead to problems with multiple path collision (two high priority objec each one one side of the door, and a low priority object in the door : it can not move, and the high priority will wait a long time)

For the room problem :

It is common to define a room as a set of tiles instead of one tile. Thus, you can define for one room, the subtiles are passable, and those that are not. if your model allows it, you can even describe the objets that are present one the different tiles and set them as impassable : the waiting room ( a 6 tiles x 4 tiles room) if fully passable, but contains a set of chairs and a small water fountain that render some subtiles impassables.

Hope this helps

Guillaume