Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
30 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

[A-Star] blocking diagonal movement

Started by
9 comments, last by Brain 13 years, 6 months ago
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]
-Jawshttp://uploading.com/files/eff2c24d/TGEpre.zip/
Advertisement
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.
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.
"Game Maker For Life, probably never professional thou." =)
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.
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.
_______________________"You're using a screwdriver to nail some glue to a ming vase. " -ToohrVyk
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
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.
_______________________"You're using a screwdriver to nail some glue to a ming vase. " -ToohrVyk
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 cd . ef g h# cardinal:if b is empty:   consider b...# diagonal:if a and (b or d) are empty:   consider a...
Create-ivity - a game development blog Mouseover for more information.
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.

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!
-Jawshttp://uploading.com/files/eff2c24d/TGEpre.zip/

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
AliAbdulKareem
Understanding the wavy-like shape in alpha-testing magnification for text rendering Graphics and GPU Programming
Advertisement

Recommended Tutorials

David Xicota
How to Expand Games (and more) Eluding App Store Updating Production and Management
GameDev.net
XM-03 3D Model Workflow Visual Arts
sortris
Google Analytics-Driven Game Development by Example Game Design and Theory
Jetpeks
From Game Prototype to Release in 2 Months Production and Management
Myopic Rhino
Writing a Font Engine General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top