- Home /
Is A* pathfinding the solution I'm looking for?
Hi, I'm building a game with a grid (two grids actually). On the grids units spawn on the bottom row and proceed to the top row of their column. If the top row is occupied they proceed to the next empty row, and so on, forming a queue. As these units are destroyed units in lower rows proceed forward to fill the gap.
Some units are faster than other units. I want these units to go around slower units and proceed to the the closest available node to the final row (this would be in the final row if it's empty or a lower row if it's not). I don't want these passing units to collide with other units.
I don't care if a unit ends up in a different column than where it started, so long as each unit ends its current movement in the center of it's square (I don't want any units wiggling around or sitting halfway between nodes if there are no better nodes available.)
I get the gist of A* and it doesn't seem difficult to implement, but are there known variants that work with multiple, ever-shifting targets? (A list of a available nodes) As opposed to a single target (like a player) which my game does not have really.
I hope this makes sense. I've included a photo for reference and I'm happy to post code or answer any questions. Thanks!
I think since your movement is up and right in case of obstacles, this could be even simpler:
move up, if free
move right if up is blocked
move down if right is blocked
wait one turn
in that order. If that's the rules of your game of course.
There are way too many open questions about your game mechanics.
Are your units required to move forward each "step" and just can decide to switch columns while the move forward?
Or can they simply move sideways without moving forward or maybe even move backwards?
You said they can move at different speeds. What is the difference ? (expressed as ratio and not absolute values)
What's the actual goal of those units? Just to get to the top line? What happens when they arrive there?
Should the top row be "filled first"? If so you might get tons of race conditions between multiple units as if one spot is empty all units would actually try to get there.
"As these units are destroyed", how are they destroyed? By the player? Which one are destroyed? only the top row units or arbitrary units on the grid?
I don't think that A* would be of much help here. ^^ In a constant changing environment it's pretty useless to actually "plan" a way from your position to a specific target as most likely several changes will happens to your path while you move towards your target. You would have to recalculate a new path each "step". Also if each unit "thinks" for itself they don't know what other units are "planning" and their plans will collide, many times, especially when they move at different speeds.
I used a couple of time the word "step". That's because since you walk on a grid you have to think in steps. Those steps can be visualized smoothly by lerping from cell to cell, but actually one state of the grid would be transformed into a new state after one "step". However that would restrict the speed differences to 2x, 3x and so on. If you want to use arbitrary speeds you can simply dump the idea of a grid since at no point in time all your units will be exactly on a grid position but most the time somewhere in between. In those cases it's getting really nasty since it's difficult to figure out when two or more units would "collide" because they want to reach the same spot.
Back on a grid system, one way to solve arbitrary speeds is that a unit that moves always occupies two grid cells (the one it comes from and the one it goes to) until it stops moving.
Your answer
Follow this Question
Related Questions
How do I do AI pathfinding in a scene that changes drastically during play 0 Answers
Public Function Acting Differently when Called by Other Script 0 Answers
How to bake navmesh on walls? 1 Answer
AI on dynamic navmeshes and moving platforms? (Drawbridges, Elevators, Monorail trains, etc) 1 Answer
Need help with a spawning system similar to Fieldrunners 2 Tower defense. 0 Answers