Im currently making my own pathing algorithm and I’m using dijkstra for it. But I can’t think of a way, how to set it so it has multible destinations like in terminal. How did other people do this?
Because right now, I do the algorithm for every possible destination and then choose the shortest path of all of those.
And this solution, well Its just slow
I also tried to use the euclidian distance, shortest one but this is not very accurate.
I did the same thing as you at first as well. In my opinion the real problem isn’t that it is slow, it depends on how you intend to use the algorithm. For example, if you were to run pathing using something else like A*, or breadth-first, etc it would be much faster than running dijkstra for every single destination. However, if you were to run say 100 different simulations, you would find that dijkstra (probably - a lot of speculation and zero hard facts here) would run faster because you only run the pathing algorithm once, whereas other implementations would run every single time.
So I don’t think you simply compare a single run between two algorithms. Dijkstra will pretty much always run slower in a single run because it is calculating unnecessary information for a single run, but that information becomes relevant if you do lots from many different spawn locations.
For me though, I left dijkstra because of the simple fact that this all assumes your map is static. The moment a blocked tile is changed you have to re-cache everything. This means if your simulator takes into consideration attacking, it slows way down. You could still do some clever caching things, etc but it becomes more complicated. This is ultimately why I stopped using dijkstra, not because of the initial slowness, but because of the slowness when updating the map. Now I do something else that I won’t go into :).
Yes, I see. I didn’t even do the caching thing, I just straigh up ran the algorithm multible times xD derp. Thats probably why mine was so slow.
While were here any ideas on how to simulate the zigzaging habit of terminals units?
Its actually not too bad. Simply keep track of which direction was done previously (horizontal vs vertical) and if there is a tie in distances between the two do the opposite of whatever was done last turn.
You don’t have to implement it in any pathing algorithms, simply do the logic when moving your units.
Ok, I get how to do it now, thanks, but what do you mean by
simply do the logic when moving your units.
I don’t quite understand where I move my units, they move on their own?
Sorry if this is a stupid question
So here are the steps I am envisioning:
So in my steps (which ignores things like: you wouldn’t want to run the pathing algorithm for every single unit, once would suffice) the pathing algorithm and when you tell the unit to move are at different times. This also makes it easier to cache the map since you just run it by itself, and then reference the output (a map of distances). Then, when something changes you just recalculate the distance map.
The distinction is that the pathing algorithm does not actually move your units, it simply tells you where the next step should be. Then you can implement the logic of zigzag when moving your units. This works because the zigzag movement only occurs when two separate paths the unit can take are equal in length.
Hope that makes sense, if not just let me know what I need to clarify further :).
Yeah I get what you mean now, I’m having some trouble coding all this but I’ll manage, thanks for the help
No problem, good luck! Feel free to message me if you have further questions about stuff that comes up :).