Sign in to follow this  
BlackShark33

[A-Star] blocking diagonal movement

Recommended Posts

BlackShark33    674
I'm working on a tower defense game, and right now when creeps calculate their path to the goal, they consider moving diagonal through towers to be acceptable, and when they try, they get stuck for obvious reasons, here is a picture to help explain,

law


How would I tell A* that such a path is not viable?
A quick hack to fix the issue would be to raise costs of all diagonal movement to something really high, that way creeps never move diagonal, however the paths are definitely not as optimal in these cases, it works but it would be nice to have a better solution.

Any suggestions?

[EDIT]
a picture of the hack
http://i135.photobucket.com/albums/q126/BlackShark33/pathfindingissuehax.png

also, I just realized this post probably belongs in the AI forums, should not be posting at 4am :o

[Edited by - BlackShark33 on October 16, 2010 7:48:59 AM]

Share this post


Link to post
Share on other sites
NDraskovic    447
Try raising the cost of tiles adjacent to the towers. This would effect the path of the creeps only when you "build" a tower and not in the open terrain, and will trigger the algorithm to find another path. You could also make an algorithm that recognizes that 2 towers are in contact at a certain point, this would tell the A* that there is no direct path between 2 diagonal tiles, and that it should find a way around.

Share this post


Link to post
Share on other sites
Rasmadrak    196
You can also use a metric - i.e if distance to next waypoint is larger than 1.4 * the length of a non-diagonal link it must be a diagonal and can be skipped.

EDIT:

My bad, did'nt notice that you didn't want to block ALL diagonal moves.

I also suggest raising the cost of adjacent tiles to each block/tower to force the units to move a bit away from the blocks.

Share this post


Link to post
Share on other sites
alvaro    21266
The obvious thing to do is to not consider that two blocks are connected diagonally if this would require passing between towers. In other words, (a, b) and (a+1, b+1) are not connected if (a, b+1) and (a+1, b) are both occupied.

Share this post


Link to post
Share on other sites
M2tM    948
If you subdivide each existing pathing tile into 9 (so divide each tile into 3 horizontal and vertical rows/columns) so you have a more fine grained grid, but if you keep the placement grid the same then you can extend the pathing blockers of each tower by 1 square (which will be 1/3 of a placement tile) and this will block diagonal movement between turrets while still allowing pathing to occur between towers not diagonally spaced.

This should allow you to avoid hacky weighted solutions or edge cases. Your pathing algorithm then also stays the same, you just have to treat your grid differently.

Grab some graph paper and try it out, you'll see it works pretty much as you describe your problem. Once you avoid treating placement/collision and pathing as the exact same tile size it actually frees things up quite a bit.

Share this post


Link to post
Share on other sites
Palidine    1315
Trivial solution:

Don't push diagonal neighbors onto the open list (or modify G for already pushed neighbors) when evaluating a given node if the cardinal nodes contain towers.

Jimmying with cost means it's still permissable to path there. The only way to tell the algorithm that it's not a valid path is to not evaluate the connection at all.

As a design feedback, tower defense games that permit diagonal movement at all should allow movement between diagonally placed towers. Most tower defense games (fieldrunners, desktop tower defense, etc) only allow cardinal movement for this reason; i.e. they don't allow diagonal movement under any circumstances.

I also don't understand why they're getting stuck. Why are you bothering to do collision detection between entities and towers in a tower defense game? It's not necessary.

-me

Share this post


Link to post
Share on other sites
M2tM    948
Just wanted to upload a quick image detailing my suggestion:



The wide black lines indicate the placement grid, the smaller tiles are the pathing grid. Dark red is the actual collision detection and placed object, it would be your turret as you have it placed. Light red is used to indicate a pathing square which is blocked off when calculating a valid path.

Quote:
As a design feedback, tower defense games that permit diagonal movement at all should allow movement between diagonally placed towers. Most tower defense games (fieldrunners, desktop tower defense, etc) only allow cardinal movement for this reason; i.e. they don't allow diagonal movement under any circumstances.

I also don't understand why they're getting stuck. Why are you bothering to do collision detection between entities and towers in a tower defense game? It's not necessary.


Don't be so quick to write off starcraft/warcraft 3 tower defense maps which popularized the genre. They allow free unit movement and support collision detection (this could make choke-points more effective). It is not unreasonable to want to simulate that.

Share this post


Link to post
Share on other sites
Captain P    1092
I'd probably ignore diagonal connections during pathfinding and smooth out the resulting path afterwards. On the other hand, as Palidine already mentioned, it shouldn't be too difficult to check whether a diagonally connected cell is blocked by two towers...

a b c
d . e
f g h

# cardinal:
if b is empty:
consider b
...

# diagonal:
if a and (b or d) are empty:
consider a
...

Share this post


Link to post
Share on other sites
alvaro    21266
Quote:
Original post by Palidine
As a design feedback, tower defense games that permit diagonal movement at all should allow movement between diagonally placed towers. Most tower defense games (fieldrunners, desktop tower defense, etc) only allow cardinal movement for this reason; i.e. they don't allow diagonal movement under any circumstances.


This is not true, at least of Desktop Tower Defense: Creeps can move diagonally, but not in between towers that touch at corners, except for a particular type of creep that does precisely that.

Share this post


Link to post
Share on other sites
BlackShark33    674
alright thanks guys!

I think I'll go with M2tM's suggestion of sub-dividing the Path-finding grid as it looks like the easiest way to accomplish this and still allow diagonal movement.

@Palidine

I use box2d to detect and react to collision with creeps and towers because some creeps will only attack towers, rather than rush to the goal, it also prevents creeps from moving through towers when they are in close proximity.


Thanks for all of you help and suggestions everyone!

Share this post


Link to post
Share on other sites
Brain    18906
Quote:
Original post by Captain P
I'd probably ignore diagonal connections during pathfinding and smooth out the resulting path afterwards. On the other hand, as Palidine already mentioned, it shouldn't be too difficult to check whether a diagonally connected cell is blocked by two towers...

a b c
d . e
f g h

# cardinal:
if b is empty:
consider b
...

# diagonal:
if a and (b or d) are empty:
consider a
...


This is exactly what i did. When tracing your path back from the target to the starting position after it is found, locate any movements that cross diagonally across a tower and insert an extra step so the character goes neatly around them, rather than through the middle. The code for that is pretty simple, and being as you already have to build this movement array usually the loop is already there so it is not impeding performace much.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this