Pathfinding
juhrjuhr.itch.io
Pathfinding
1–10 of 48 posts
Re: Pathfinding
#2One efficiency update you can make is that if background objects don’t move, then you don’t need to recalculate the path. So check if anything moved before recalculating.
Re: Pathfinding
#3One efficiency update you can make is that if background objects don’t move, then you don’t need to recalculate the path. So check if anything moved before recalculating.
That's true until the map itself changes, eg other objects moving around in the calculated path
Re: Pathfinding
#4One efficiency update you can make is that if background objects don’t move, then you don’t need to recalculate the path. So check if anything moved before recalculating.
That's true until the map itself changes, eg other objects moving around in the calculated path
Yeah I said that. If nothing moves. No need to change.
Re: Pathfinding
#5Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations.
The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.
Re: Pathfinding
#6Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations. The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.
Re: visualizations, yeah, it’s really easy to caught up in playing with the algorithm just to watch it run rather than using it in your project. Been there, did that. For two distinct projects.
Re: Pathfinding
#7I remember fondly messing around with some pathfinding with some friends in my 20s and adding random amounts of cost to nearby nodes. This has the distinct effect of making NPCs meander around, or follow a "drunken path."
Re: Pathfinding
#8See also https://www.redblobgames.com/pathfinding/a-star/introduction...
One of the first games I ever played was Warcraft I, and it was one of the games I always wanted to make but never could. One of the missing pieces of the puzzle was path finding. I still don't understand it, but at least now I have two resources that I can read when I'm done building my game maker and ready to make my game!
Re: Pathfinding
#9Neat article!
This will depend on the type of game or application, but one thing I've been doing is to do the more rigorous pathfinding when the environment (collision map) changes in order to generate a sort of precomputed pathfinding map (grid, or graph). When I search a path, or route for an entity, then it's on that pathfinding map.
Again, it depends on how that simulation fundamentally works. Some have natural POIs, crossroads and corners that one can work with. Others might need some heuristics to determine those or merge together paths. It might also be worth trying to use a very coarse logic for gross movement but adjust the actual path moment to moment, but that's just an idea that I never tried.
The approach in the article is of course very dynamic, which has the advantage of being excellent at trying stuff out and visualizing it.
I personally never tried out the space partitioning mentioned in the article and don't understand it fully. But there might be strong similarities to what I described above.
Re: Pathfinding
#10See also https://www.redblobgames.com/pathfinding/a-star/introduction... One of the first games I ever played was Warcraft I, and it was one of the games I always wanted to make but never could. One of the missing pieces of the puzzle was path finding. I still don't understand it, but at least now I have two resources that I can read when I'm done building my game maker and ready to make my game!
WC1 has fairly blocky movement and is grid based. It seems like units literally move from tile to tile so to speak.
If this is actually the case, you could try the Lee algorithm: https://en.wikipedia.org/wiki/Lee_algorithm. It's extremely simple and effective.
You might want to try adjusting it for diagonal movement and you probably don't want to store obsolete path sections, but only turns.