Hello guys.

I have a* implemented in my game, the algorithm knows which tiles are walkable and which ones are not, but does not know about enemies.

While performing a path, if my character collides with an enemy, it will declare unwalkable the tiles that the enemy is standing on, which can be from 1 to 4 tiles (the enemy can be in the middle of 4 tiles).

To understand my problem, you have to understand how I execute a path after I found it.


The tile my char is standing on, is the origin tile for the pathfinding, but the character doesnt need to be in the middle of the tile exactly, as the game moves the character pixel by pixel, so, the first move my character makes, is going to the center of the origin tile.

Now, consider this:

Im following my path.

I found an enemy.

The enemy is located within a tile, I declare that tile as unwalkable.

I start my pathfinding... OH DAMN, my origin tile is the tile where my character is located, which happens to be the same tile where the enemy is, and I cant move to the center of this tile, because my enemy's collision radius (which I use to calculate collisions between characters) envolves the center of the tile.

So now im on a dead lock, I have to move to the center of the tile, but the character to character collision avoidance does not allow that, but my movement system needs to move there to proceed.

I am having a big head ache to find out how to get this done.

One of my problems is that my characters ONLY move in 8 directions (multiples of 45 degrees), that why I move to the center of the first tile, because after that, I will only have to move straight up/down left/right or in straight diagonals from the center of a tile to the center of the next tile till I find my goal.

I think I have spoken a lot, but this has been bugging me for a long time, and I have failed to find a way to get this done.

[Edited by - arthurviolence on December 27, 2010 11:04:57 AM]

Calc the path anyway and see if you can get to the next node... i.e. skip the center of the tile you are in. Remember, tiles and such are arbitrary constructs so we can use arbitrary overrides to those rules.

Suppose Im going from A to D

The blue circle is the player, the red circle is an enemy.
I cant reach the center of the B node, because the enemy is above it.

I also cant reach the next node, because the enemy is in the way, so I have to tell the pathfinding algorithm, in the next search, that the tile the player is standing on is not walkable, and I have to find a new node to be the first node.

If the B node is interpreted as the source node, the algorithm WILL see the C node as the next one, but theres no way to reach it.

Ideally, the new first node should be the one directly above or directly left of B.

Im struggling to tell the algorithm to go back a little to find another first node because that one is invalid.

One approach is to use local steering to get around local objects. That has nothing to do with your graph and is simply free movement to get around objects.

However, I believe that most of your problem stems from the premises that you have put in place. e.g. "I can't use a node as an initial node if the enemy is is in it." Why not?

Because considering the node that the enemy is on as the initial node will lead to to the second node being one that is behind the enemy, which leads to the situation I described above.

Im in a place, trying to move to another place, with someone between. I can try to reach that place anyway, but I will just keep bumping into the enemy that is in the way.

What I'm saying is that either you have nodes or you don't. In your world, if you are in a square, you are legitimately IN a square. Therefore, you can use that node. Your problem stems from the fact that the enemy is in a square but knows nothing of nodes. One way around it is to use a LOS check between nodes to make sure that the edge you want to traverse is actually free. If it is not, your A* will take the other edges into account and make you go around the enemy.

The whole point, however, is that you are using this arbitrary construct (nodes) and letting it completely define you. Step away from the construct and make some new rules. As I mentioned before, a common technique is local steering. Yes, you are trying to get from A to B, but in the mean time, you have to do obstacle avoidance in order to get to B. Look up steering behaviors.

I am having a little trouble understanding you, sorry (English is a knife in my back sometimes), but the message is coming through now.

I guess you're right, I will try to think outside the box now and take a look at steering behaviors, I was thinking about doing that before.

Will find a way to solve this thing.

Thank you for the advice.