(I am not certain whether this post should be here or in the Design Philosophy section. I don't have a specific code problem per se, as it's probably more general, and Design Philosophy seems more about the design of the game from a player's POV. I apologize in advance and ask that someone move this for me if I am mistaken.)
Hello BYOND community!
I am beginning preliminary work/research for an RTS-like building game where each player will control several units at once. The world should be able to change dynamically at any time through walls being built and destroyed, etc. I'm looking for suggestions for how I can implement pathfinding for each unit that will allow me to have a starting point I can modify later as I better realize the needs of my game.
I have already successfully implemented an A* method on my own, based on the popular article here and the Wikipedia article on A*. However, the method I created is terribly inefficient and I'm not certain how well it will scale up. I also need to allow units to find their way through multiple z-levels via stairs/ladders, and I'm not sure how I could best handle that either.
Thank you!
When you have doors/stairs/etc, you need to create your own path finding, otherwise the mob would stay on the wrong location forever.
| |
The built in pathfinding procs are ... decent, to say the least. However, I'm looking for more flexibility than what walk_to and similar procs provide out of the box. Thanks, though! :)
| |
What does walk_to not do that you need to it do?
I mean, it's just an RTS. There shouldn't be doors and stairs to worry about. It's just a flat world with buildings on it. No really complex structures to navigate. | |
Well, he mentioned that the units in the game need to move through the different z-levels, if any TheLionsRoar could check the closest stairs/ladders and make the units move to them, and then continue their normal path as long as they were on the correct z-level.
| |
I did say that my game is an RTS-like. I only mention RTS because each player would be controlling multiple units. Dwarf Fortress or Gnomoria would be greatly exaggerated examples of what I'd like to do. Doors and stairs are a requirement, as my game does not have a flat, single level world. :)
| |
Okay, right. Well, you didn't pick an easy problem. Best of luck with that. If I was good enough to help, trust me I'd try.
| |
The problem is that there may be many obstacles in the mob's path, what would you like to do if the mob can't reach stairs/ladders? You could check all the stairs in the z-level once, and then compare the distance between the mob and the object. However, this wouldn't fix the problem because you'd need to calculate if there's any obstacle in the path. You could use walk_to on the closest stair, and then check every 5 seconds if the mob's location is simillar to the previous one (you'd need to update that "Old Location" every 5 (or w.e.) seconds). After that you could add the stairs to a list which the mob'd ignore while searching for a new path, this'd be rather exhausting and you might want something different in your game, perhaps the ability of creating stairs if you can't go through any?
| |
Hm, I did not think of the case where stairs/ladders are not be reachable. I figure I can solve that myself with some work, I just wanted to mention multiple z-levels in my initial post for completeness.
I'm more worried about handling dynamic obstacles that may require a change in a mob's path. I still do not think that using walk_to is a good choice for me, for reasons given by Ter13 in this response. I suppose that my concerns are a follow-up to his suggestions, based on the needs of my game. | |
Zecronious wrote:
What does walk_to not do that you need to it do? Not completely shit on your CPU usage. | |
I haven't tested this resource myself but A* is one of the standard pathfinding algorithms.
| |
Ter13 wrote:
Zecronious wrote: Absolutely. Any test case I've made with it using a fairly decent amount of mobs would have terrible CPU usage. I imagine it would be all right to be called once in awhile, but I need something that can be called near constantly. Lugia319 wrote: I haven't tested this resource myself but A* is one of the standard pathfinding algorithms. In the past I have used that or Deadron's similar library, and both provide decent results. However, I'm still looking to implement a more custom solution. Those libraries can be terrible to debug or modify/extend with custom behavior, as they're meant to be "one size fits all" in the same sense as the built-in functions. Thanks for all of your suggestions, though! I'm just looking for something a bit more than what is easily accessible now. :) | |
How laggy is step_to() though? It shouldn't lag that much unless you have a lot of mobs moving at the same time.
| |
Easily just as much, though that would not help any more than walk_to does. I intend to have 50+ mobs moving at the same time, in addition to the flexibility of customization that my game requires.
| |
Eternal_Memories wrote:
How laggy is step_to() though? It shouldn't lag that much unless you have a lot of mobs moving at the same time. Incredibly. The more steps in a path, the more problematic it is. It's a horrible implementation, but it's the best that BYOND can do for a number of reasons. BYOND's implementation isn't all that bad, it's just naive. As such, it's something you probably shouldn't use when the possibility of a proper A* algorithm does in fact exist. Using my own pathfinding algorithm, I've been able to have 70K mobs moving at once in the world. Using step_to(), I cap out around 150. | |
Ter13 wrote:
Using my own pathfinding algorithm, I've been able to have 70K mobs moving at once in the world. Wow, that is impressive. Would you be willing to share your algorithm, or at least how you arrived at it? I have not yet had time today to further my own attempts, but I am willing to expand my naive understanding. | |
My approach was a basic A* that cached its results in a vector path datum. The trick is to cache the path, rather than regenerating a the path every tick.
There was nothing horribly special about the approach. | |
That is what I began to do in my implementation, and it is much nicer. How would you handle a path needing recalculated (e.g. because a mob moved to block a narrow passage)?
| |
I didn't need to. I just waited until the mob bumped into another mob and re-pathed from there.
| |
Pathfinding is built in. Just use the process again whenever and it will cancel the last walk_to that you issued.
I don't see why you would write your own path finding in BYOND instead of using that time to build the game.