From what I hear, he doesn't even use proper programming techniques like encapsulation. I think he just copies and pastes similar code if he needs to do something more than once instead of writing a method that uses it.
How can people know if nobody has seen the source?
Non-programmers have a very different idea of what decompilers are capable of from what programmers know. They are not nearly as useful as you may think they are.
I suppose there is also the point that the game is procedurally generated, and keeps track of far more statistics on each creature than your regular game. I mean, Sim city, you might have a million sims, but it's not keeping track of, for example, how often each sim is blinking, when they need to blink, if they have eyelids, etc, etc, just for a start. Dwarf fortress handles a very large amount of data per "Living" object.
However, I've no idea how much impact keeping track of every single function of every dwarf might be, especially considering toady's apparently somewhat amateur programming efforts
I suppose there is also the point that the game is procedurally generated, and keeps track of far more statistics on each creature than your regular game. I mean, Sim city, you might have a million sims, but it's not keeping track of, for example, how often each sim is blinking, when they need to blink, if they have eyelids, etc, etc, just for a start. Dwarf fortress handles a very large amount of data per "Living" object.
However, I've no idea how much impact keeping track of every single function of every dwarf might be, especially considering toady's apparently somewhat amateur programming efforts
Even then, it really makes a difference on how he is manipulating the data. It involves some non-trivial math, but time-complexity algorithms are studied precisely for this reason. The difference between a sorting algorithm that runs O(n) and one that runs in O(n log n) can make a significant difference when you are working with even moderately sized data sets. Additionally, it really matters in how he is addressing his problems. He needs to be structuring his problems to that they are not NP-Complete (exponential with respect to the size of the input). I can't really say much more without knowing how he searching for his solutions, but I can honestly say that there is nothing that he needs to be doing that can't run at optimal speed given the right data structures, code design, and algorithms.
Even then, it really makes a difference on how he is manipulating the data. It involves some non-trivial math, but time-complexity algorithms are studied precisely for this reason. The difference between a sorting algorithm that runs O(n) and one that runs in O(n log n) can make a significant difference when you are working with even moderately sized data sets. Additionally, it really matters in how he is addressing his problems. He needs to be structuring his problems to that they are not NP-Complete (exponential with respect to the size of the input). I can't really say much more without knowing how he searching for his solutions, but I can honestly say that there is nothing that he needs to be doing that can't run at optimal speed given the right data structures, code design, and algorithms.
That makes pretty good sense - after all, even if you are keeping track of how gritty each creature's individual eyes are, there should be an efficient way to log, find, modify or create that data.
Actually, I think, based on this, that part of Toady's problem is that, to paraphrase slightly, he is trying to do to much with eet. He's focusing on a bunch of stuff that could wait, instead of optimising what he has to run better. I mean, the one tile hallways thing should be an issue of common sense and decent planning - it's a dwarf fort, not a snakepit, they're not gonna be climbing all over each other all the time - rather than an issue of necessity because of the code.
Unless he open-sources it all, that would be pointless. You can't patch a bug you can't see. We have no idea what convoluted shenanigans are going on in there.
If you require knowledge of any code to write a path finding algorithm from scratch and mail that to him and tell him it's the best way to deal with pathfinding in DF's changing 3D grid that works on many dozens of creatures (instead of just 1 dozen creatures on pre-made nodepaths in a static environment you find in most games these days), then you're just as shitty a programmer as Toady. All that happens to path finding code is that it gets called, optionally with the location of an obstacle, and returns a path, nothing more, nothing less. You do not need to know shit about why the path finding was called.
The only computer games that are like that are old Atari Chess games. The pathfinding DF does is simple: it's 100% the fault of bad code that it's so slow and unscalable.
I didn't talk about just turn-based VIDEO-games. Or are you trying to tell me that I can just keep moving my pieces while you think and declare checkmate?
Are you kidding? Pathfinding is probably second only to sorting in terms of being the most-looked-at computer science problems in the history of computing. I highly doubt that the DF pathing requirements are both novel and nontrivial: they are likely a solved problem. Again, all that needs to happen is for one smart CS professional to actually examine and rewrite the code.
Yes, path finding is a thoroughly researched computing problem. It is also still slow due to the inherent nature of the problem. Multiply that by dozens of creatures wanting to path over large distances as fast as possible through a ridiculously inefficient user-created system of paths and you get very slow.
Oh my bad, it's consumer hardware.
No, it's you. Being stupid. Demanding that your hardware performs outside of its capabilities without any noticeable side-effects, and then crying when it slows down a bit. It cannot magically perform more calculations per second, and thus has to spend more time finding the solutions to the problems that arise due to your crappy designing. You suck as much as toady in that regard.
Oh, yeah, the same consumer hardware that can render HD video, match proteins, search for aliens in space, trivially perform complex relational joins. Yeah, that same consumer hardware.
The only one of those that actually makes sense to compare to DF is decoding video since that too has a speed requirement for a good experience, the others do not care how fucking long they take to compare one protein to another, etc. What you were doing with DF is equivalent to demanding smooth playback of a 1080p H.264 encoded video of an action scene on the first netbook. I doubt your current laptop with it's integrated Intel graphics card can do that. Before you whine, YES, this is a slightly exaggerated version of your demands, fuck you.
Every play Sim City 2000 on some modern hardware? Notice when you put it in Cheetah speed mode it goes so fast you can't even see what's going on? Dwarf Fortress would go even faster than that if coded properly. It's painfully obvious to anyone who knows anything about computers that it is probably one of the worst-coded things I've ever seen. I'm amazed that it even works.
Are you seriously saying that a game that only keeps track of the number of matches in one matchbox will be outpaced by one that keeps track of the number of matches in a match-factory on the same hardware?
EDIT:
Actually, I think, based on this, that part of Toady's problem is that, to paraphrase slightly, he is trying to do to much with eet. He's focusing on a bunch of stuff that could wait, instead of optimising what he has to run better.
And thus we come to the person, Toady. He has created a game that runs, appears complex, is very enjoyable, and makes him enough money to not have to work. The game is not programmed super efficiently and he knows that. So he fears he might lose this easy going no-job life if he open sources the entire thing, and that he might lose control over it since it is the project of his brother and he. Can you blame him? Not everyone is perfect.
Yes, path finding is a thoroughly researched computing problem. It is also still slow due to the inherent nature of the problem. Multiply that by dozens of creatures wanting to path over large distances as fast as possible through a ridiculously inefficient user-created system of paths and you get very slow.
Path finding algorithms (going from point A to point B in minimum length) can run in O(|E|log|V|) for sparse graphs or O(|V|^2) (polynomial time).This is about as fast as one can get, unless you know some crazy awesome algorithm. If it's slow, it's only because he isn't implementing it correctly in which case he either needs to get his code peer reviewed or open source it. However, more difficult problems such as TSP or Hamiltonian cycles are NP-Complete. Again, it all matters in how he is approaching the issue and what problem he is trying to solve.
No, it's you. Being stupid. Demanding that your hardware performs outside of its capabilities without any noticeable side-effects, and then crying when it slows down a bit. It cannot magically perform more calculations per second, and thus has to spend more time finding the solutions to the problems that arise due to your crappy designing. You suck as much as toady in that regard.
Even a shitty laptop should be able to perform any necessary calculations that DF needs to run well. It's not a matter of expecting one's hardware to perform outside of it's capabilities, but rather expecting someone to write code correctly so the hardware doesn't have to do any unnecessary work.
The difference between a sorting algorithm that runs O(n) and one that runs in O(n log n) can make a significant difference when you are working with even moderately sized data sets.
Heh, O(n) sorting algorithms aren't particularly general-purpose though. Now, the difference between O(n log n) and O(n^2) is rather important, but anyone with any sense will at least be using the default sorting algorithm in whatever library is applicable, and that will definitely be O(n log n).
Yes, path finding is a thoroughly researched computing problem. It is also still slow due to the inherent nature of the problem. Multiply that by dozens of creatures wanting to path over large distances as fast as possible through a ridiculously inefficient user-created system of paths and you get very slow.
Path finding algorithms (going from point A to point B in minimum length) can run in O(|E|log|V|) for sparse graphs or O(|V|^2) (polynomial time).This is about as fast as one can get, unless you know some crazy awesome algorithm. If it's slow, it's only because he isn't implementing it correctly in which case he either needs to get his code peer reviewed or open source it. However, more difficult problems such as TSP or Hamiltonian cycles are NP-Complete. Again, it all matters in how he is approaching the issue and what problem he is trying to solve.
That's true. Sometimes you have to accept that a slightly less-than-perfect solution in O(n log n) is far better than a completely perfect solution in exponential time.
I haven't played DF, but from what I've read it should definitely run much better than it does. For a start, it should have been multithreaded from the ground up, though better algorithms would likely have far more impact than threading.
Unless he open-sources it all, that would be pointless. You can't patch a bug you can't see. We have no idea what convoluted shenanigans are going on in there.
If you require knowledge of any code to write a path finding algorithm from scratch and mail that to him and tell him it's the best way to deal with pathfinding in DF's changing 3D grid that works on many dozens of creatures (instead of just 1 dozen creatures on pre-made nodepaths in a static environment you find in most games these days), then you're just as shitty a programmer as Toady. All that happens to path finding code is that it gets called, optionally with the location of an obstacle, and returns a path, nothing more, nothing less. You do not need to know shit about why the path finding was called.
You do, however, need to know about the nature of the data structures that hold all of the data you need to work with.
Oh my bad, it's consumer hardware.
No, it's you. Being stupid. Demanding that your hardware performs outside of its capabilities without any noticeable side-effects, and then crying when it slows down a bit. It cannot magically perform more calculations per second, and thus has to spend more time finding the solutions to the problems that arise due to your crappy designing. You suck as much as toady in that regard.
Oh, yeah, the same consumer hardware that can render HD video, match proteins, search for aliens in space, trivially perform complex relational joins. Yeah, that same consumer hardware.
The only one of those that actually makes sense to compare to DF is decoding video since that too has a speed requirement for a good experience, the others do not care how fucking long they take to compare one protein to another, etc. What you were doing with DF is equivalent to demanding smooth playback of a 1080p H.264 encoded video of an action scene on the first netbook. I doubt your current laptop with it's integrated Intel graphics card can do that. Before you whine, YES, this is a slightly exaggerated version of your demands, fuck you.
Actually, pretty much any integrated graphics chip with support for hardware H.264 acceleration will handle 1080p H.264 pretty well.
If you require knowledge of any code to write a path finding algorithm from scratch and mail that to him and tell him it's the best way to deal with pathfinding in DF's changing 3D grid that works on many dozens of creatures (instead of just 1 dozen creatures on pre-made nodepaths in a static environment you find in most games these days), then you're just as shitty a programmer as Toady.
You really don't understand how coding works, eh? Without knowing his architecture and internal interfaces, writing a patch would be an exercise in futility, re-inventing the wheel and interacting with a black box. Google could tell him what to do conceptually, but his architecture is probably sloppy and difficult to work with.
All that happens to path finding code is that it gets called, optionally with the location of an obstacle, and returns a path, nothing more, nothing less. You do not need to know shit about why the path finding was called.
Again, you have no idea what you're talking about. Pathfinding can be parallelized. Furthermore, non-relevant or non-visible pathfinding can be aggregated in many cases. He probably procedurally generates paths out from objects based on objectives in a single-threaded, monolithic, inefficient manner. Far more complex systems manage far more unit complexity with less power. Consider particle effects, for example.
I didn't talk about just turn-based VIDEO-games. Or are you trying to tell me that I can just keep moving my pieces while you think and declare checkmate?
Those old games took forever to decide on a move because they were coded in shitty, brute-force ways. DF is basically the same way. It very likely wastes most of the CPU cycles it uses.
Yes, path finding is a thoroughly researched computing problem. It is also still slow due to the inherent nature of the problem. Multiply that by dozens of creatures wanting to path over large distances as fast as possible through a ridiculously inefficient user-created system of paths and you get very slow.
Not nearly as slow as it does. There are likely a small number of logical bottlenecks in the algorithms he's using, which themselves could be made more efficient. He could also asynchronously process non-visible or far-away complexity whenever possible. Nevermind the fact that he probably doesn't use any sort of intelligent algorithm switching depending on the circumstances.
I'll bet good money that a few weeks of competent code review could increase the speed of the game by an order of magnitude with no loss of gameplay complexity.
No, it's you. Being stupid. Demanding that your hardware performs outside of its capabilities without any noticeable side-effects, and then crying when it slows down a bit. It cannot magically perform more calculations per second, and thus has to spend more time finding the solutions to the problems that arise due to your crappy designing. You suck as much as toady in that regard.
But what DF is doing is relatively simple compared to many of the things other programs do. It's slowing down because it constantly engages in inefficient processes. The fact that DF scales so unbelievably poorly is testament to the fact that it's doing something WRONG.
I doubt your current laptop with it's integrated Intel graphics card can do that. Before you whine, YES, this is a slightly exaggerated version of your demands, fuck you.
You overestimate the true complexity of DF while simultaneously underestimating the complexity of video.
And thus we come to the person, Toady. He has created a game that runs, appears complex, is very enjoyable, and makes him enough money to not have to work. The game is not programmed super efficiently and he knows that. So he fears he might lose this easy going no-job life if he open sources the entire thing, and that he might lose control over it since it is the project of his brother and he. Can you blame him?
It's only a matter of time before other people do exactly what he did but a thousand times better. Keeping it closed damns it to never progressing much past where it is now, eventually to be overtaken by something new. DF, unless it opens up, has zero future.
Yo have a big old grid, a few thousand by a few thousand squares. Some number of squares on the grid are impassable, but every passable square is guaranteed to have a path to every other passable square. Now, a few thousand dwarfs are randomly placed on passable squares. Each dwarf is assigned a random destination square, that is passable and reachable. Each dwarf moves at a speed of one square per "turn" in any direction, including diagonally, and no two dwarfs may occupy the same square on the same "turn". Also, no two dwarves have the same destination. Using A*, or another pathfinding algorithm, get all dwarves to their destinations in the smallest number of turns. Draw a line representing the path of each dwarf.
I can tell you, that if coded properly, this program will basically run almost instantly on a modern computer for a very large number of dwarves. As soon as you press the solve button, the solution will appear. If you code it to give each dwarf a new destination every time they reach their goal, you will basically see a flickering screen full of dwarves moving like lightning. I almost want to code just this part now. I bet it will be instant in python, but it would be even more instant in C. Java or C# would be good choices as well. Maybe I'll do it in XNA. XBox Dwarf Fortress? Probably don't even need to do multi-threading, but a thread for each dwarf would be pretty awesome.
Also, it will be interesting to see what kind of weird bugs show up with the dwarf interactions, and how to work around them. I can already see two dwarves at opposite ends of a tunnel going back and forth as they block each other, and then unblock each other in a loop.
I wouldn't mind playing with that myself. The grid would be 3-D, mind you, but that doesn't really make all that much difference apart from increasing the branching factor. A* is quite good as long as you don't run into memory limitations, but a search space of a few million grid squares is really quite small.
Additionally, even if this were to prove slower than preferable, it's entirely reasonable to drop the requirement that the dwarves take the absolute best path to their destination. After all, they're just dorfs, and who would expect a bunch of dorfs to find the absolute best path every single time?
Additionally, even if this were to prove slower than preferable, it's entirely reasonable to drop the requirement that the dwarves take the absolute best path to their destination. After all, they're just dorfs, and who would expect a bunch of dorfs to find the absolute best path every single time?
I'm not a programmer, but do these path finding algorithms rate the paths? Such as, Path A is a 55, Path B is a 0, Path C is a 90, so take Path C? It seems to me it would be easier to just tell them to use a path that's above an 85 or something, and pass those processing cycles to the next dwarfs path finding.
Edit: Upon further review, this may be how path finding already works. :P
Double Edit!: Why not have the quality of the path change based on processor utilization? With 10 dorfs it might be a 98, but with 50 dorfs it might be a 85.
Additionally, even if this were to prove slower than preferable, it's entirely reasonable to drop the requirement that the dwarves take the absolute best path to their destination. After all, they're just dorfs, and who would expect a bunch of dorfs to find the absolute best path every single time?
I think the tougher requirement is that two dwarfs can't be in the same spot on the same turn. Without that requirement, you can trivially iterate down the list of dwarfs running A* on each one, and that's it. Because of this requirement, you have to do A* for one step on every dwarf. Then do another step on every dwarf. And each step there will be these moving obstacles, the other dwarves. Moving obstacles make it really hard because the algorithm might close a particular path that isn't necessarily closed.
I think the tougher requirement is that two dwarfs can't be in the same spot on the same turn. Without that requirement, you can trivially iterate down the list of dwarfs running A* on each one, and that's it. Because of this requirement, you have to do A* for one step on every dwarf. Then do another step on every dwarf. And each step there will be these moving obstacles, the other dwarves. Moving obstacles make it really hard because the algorithm might close a particular path that isn't necessarily closed.
A better heuristic would probably be to only generate a path if it doesn't have one already or if it has reached an obstacle. Furthermore, you should allow dwarves to pass through each other albeit at a time penalty (gotta take the time to squish past each other).
Furthermore, you should allow dwarves to pass through each other albeit at a time penalty (gotta take the time to squish past each other).
That would achieve almost the same effect, as dwarves might choose a different path if the cost of squishing made another path more optimal. But it loses all the interesting gotcha situations.
Imagine two dwarfs staring at each other down a long tunnel that is one dwarf wide. They both have goals at opposite ends of the tunnel, and would both use it without question if no other dorfs were around. Which dorf ends up taking the long way around? What if there is no other way around? Can you get one of them to wait on their end of the tunnel for the other one to come through? How do you decide which one has to wait?
Make it even worse. Let's say you have the two dwarfs coming to the narrow tunnel. One gets their first, and starts using it. Another one shows up, and doesn't use it because it's blocked, so he takes the long way around. However, it would have actually been better for the one who took the long way around to use the tunnel, and for the guy who got their first to wait.
Here's the stinkiest I could come up with. There's a dwarf whose goal location is in the middle of the narrow tunnel. He starts just outside of it, goes in, and stands there not moving. Now it's permanently blocked. If he just waited at his starting spot, all the other dwarves could have used the tunnel to great speed up effect. Instead, it's blocked up because of one dick.
So, I wrote a small program to give people an idea of just what we are talking about. The below python program calculates the nth number of the Fibonacci sequence in two different ways.
The first is an iterative method while the second is a recursive method. To give you an idea, to calculate n=45, it takes the iterative method about 90 steps while the recursive method takes over a billion steps. import os def goodFib(num): fibs = [1,2] for x in range(2, num): fibs.append(fibs[x-1] + fibs[x-2]) return fibs[num - 1]
def badFib(num): if (num == 0 or num == 1): return 1 else: return badFib(num - 1) + badFib(num - 2)
Additionally, even if this were to prove slower than preferable, it's entirely reasonable to drop the requirement that the dwarves take the absolute best path to their destination. After all, they're just dorfs, and who would expect a bunch of dorfs to find the absolute best path every single time?
I think the tougher requirement is that two dwarfs can't be in the same spot on the same turn. Without that requirement, you can trivially iterate down the list of dwarfs running A* on each one, and that's it. Because of this requirement, you have to do A* for one step on every dwarf. Then do another step on every dwarf. And each step there will be these moving obstacles, the other dwarves. Moving obstacles make it really hard because the algorithm might close a particular path that isn't necessarily closed.
You know, that 's a very good point, and actually makes this problem interesting enough to be worth looking into. It would be fun to set up a framework for the problem and play with various approaches.
Andrew's solution of letting dwarves squeeze past each other is helpful, although if dwarves squeezing past each other still has a move penalty the complexity of the problem remains relatively high - unless you're willing to accept suboptimal solutions.
The other interesting thing about the issue is that although the globally optimal solution would be that the sum of the lengths of the paths is minimized, the locally optimal solution from each dwarf's point of view would probably involve a fight.
So, I wrote a small program to give people an idea of just what we are talking about. The below python program calculates the nth number of the Fibonacci sequence in two different ways.
The first is an iterative method while the second is a recursive method. To give you an idea, to calculate n=45, it takes the iterative method about 90 steps while the recursive method takes over a billion steps.
Your default test is somewhat mean-spirited, and goodFib is somewhat wasteful with memory, but it's a good demonstration nonetheless.
I had this screenshot of code Toady once posted on the DF forums asking for coding help. It was such a nightmare that even I, in my limited programming experience, could see the inefficiency of it. It was a piece of code that was intended to recognize keystrokes. It utilized a recursive method to do so. Nightmarish.
So, since I really doubt he'll release the source, maybe we can glean some information by looking at the source of his first game, Slaves to Armok.
Here's a blog talking about porting it over to mac, but they have the source available for download.
Once again, I'm not a programmer, but I've been looking for some path finding in this code. So far I have this...
void unitst::move_randomly() { //IF YOU ALREADY HAVE A PATH, KEEP FOLLOWING IT if(path_x.size()>0) { if(game.cave.walkable(path_x[0],path_y[0],this,1)) { x=path_x[0]; y=path_y[0];
path_x.erase(0); path_y.erase(0);
return; } }
//OTHERWISE MOVE RANDOMLY short sx=0; short sy=0; if(trandom(2))sx=trandom(2)*2-1; else sy=trandom(2)*2-1;
From what I've read, he used A* for pathfinding in DF, and it's unlike his other code. Also, it looks like game.cave.buildpath holds the actual pathfinding code; what you posted just covers movement. Given the use of erase(), I hope that's a linked data structure he's using for the paths there.
short linecheck=0; short lineplace=1; long curchecklim=1,curplacelim; line[linecheck][0][0]=gx; line[linecheck][0][1]=gy; long fill=path_start+1; long maxpass=2000;
It took me a while to recognise it, but it seems that he's filling a grid using Dijkstra's algorithm, and making a path by traversing randomly up squares that are increasingly close (in true distance) to the goal. Not a good approach, overall. The way he's done the randomization only serves to slow things down, and Dijkstra's algorithm is a poor choice given the situation.
At least this isn't what's used in Dwarf Fortress.
Comments
However, I've no idea how much impact keeping track of every single function of every dwarf might be, especially considering toady's apparently somewhat amateur programming efforts
Actually, I think, based on this, that part of Toady's problem is that, to paraphrase slightly, he is trying to do to much with eet. He's focusing on a bunch of stuff that could wait, instead of optimising what he has to run better. I mean, the one tile hallways thing should be an issue of common sense and decent planning - it's a dwarf fort, not a snakepit, they're not gonna be climbing all over each other all the time - rather than an issue of necessity because of the code.
EDIT: And thus we come to the person, Toady. He has created a game that runs, appears complex, is very enjoyable, and makes him enough money to not have to work. The game is not programmed super efficiently and he knows that. So he fears he might lose this easy going no-job life if he open sources the entire thing, and that he might lose control over it since it is the project of his brother and he. Can you blame him? Not everyone is perfect.
I haven't played DF, but from what I've read it should definitely run much better than it does. For a start, it should have been multithreaded from the ground up, though better algorithms would likely have far more impact than threading.
Not nearly as slow as it does. There are likely a small number of logical bottlenecks in the algorithms he's using, which themselves could be made more efficient. He could also asynchronously process non-visible or far-away complexity whenever possible. Nevermind the fact that he probably doesn't use any sort of intelligent algorithm switching depending on the circumstances.
I'll bet good money that a few weeks of competent code review could increase the speed of the game by an order of magnitude with no loss of gameplay complexity. But what DF is doing is relatively simple compared to many of the things other programs do. It's slowing down because it constantly engages in inefficient processes. The fact that DF scales so unbelievably poorly is testament to the fact that it's doing something WRONG. You overestimate the true complexity of DF while simultaneously underestimating the complexity of video. It's only a matter of time before other people do exactly what he did but a thousand times better. Keeping it closed damns it to never progressing much past where it is now, eventually to be overtaken by something new. DF, unless it opens up, has zero future.
Yo have a big old grid, a few thousand by a few thousand squares. Some number of squares on the grid are impassable, but every passable square is guaranteed to have a path to every other passable square. Now, a few thousand dwarfs are randomly placed on passable squares. Each dwarf is assigned a random destination square, that is passable and reachable. Each dwarf moves at a speed of one square per "turn" in any direction, including diagonally, and no two dwarfs may occupy the same square on the same "turn". Also, no two dwarves have the same destination. Using A*, or another pathfinding algorithm, get all dwarves to their destinations in the smallest number of turns. Draw a line representing the path of each dwarf.
I can tell you, that if coded properly, this program will basically run almost instantly on a modern computer for a very large number of dwarves. As soon as you press the solve button, the solution will appear. If you code it to give each dwarf a new destination every time they reach their goal, you will basically see a flickering screen full of dwarves moving like lightning. I almost want to code just this part now. I bet it will be instant in python, but it would be even more instant in C. Java or C# would be good choices as well. Maybe I'll do it in XNA. XBox Dwarf Fortress? Probably don't even need to do multi-threading, but a thread for each dwarf would be pretty awesome.
Also, it will be interesting to see what kind of weird bugs show up with the dwarf interactions, and how to work around them. I can already see two dwarves at opposite ends of a tunnel going back and forth as they block each other, and then unblock each other in a loop.
Additionally, even if this were to prove slower than preferable, it's entirely reasonable to drop the requirement that the dwarves take the absolute best path to their destination. After all, they're just dorfs, and who would expect a bunch of dorfs to find the absolute best path every single time?
Edit: Upon further review, this may be how path finding already works. :P
Double Edit!: Why not have the quality of the path change based on processor utilization? With 10 dorfs it might be a 98, but with 50 dorfs it might be a 85.
http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html
Imagine two dwarfs staring at each other down a long tunnel that is one dwarf wide. They both have goals at opposite ends of the tunnel, and would both use it without question if no other dorfs were around. Which dorf ends up taking the long way around? What if there is no other way around? Can you get one of them to wait on their end of the tunnel for the other one to come through? How do you decide which one has to wait?
Make it even worse. Let's say you have the two dwarfs coming to the narrow tunnel. One gets their first, and starts using it. Another one shows up, and doesn't use it because it's blocked, so he takes the long way around. However, it would have actually been better for the one who took the long way around to use the tunnel, and for the guy who got their first to wait.
Here's the stinkiest I could come up with. There's a dwarf whose goal location is in the middle of the narrow tunnel. He starts just outside of it, goes in, and stands there not moving. Now it's permanently blocked. If he just waited at his starting spot, all the other dwarves could have used the tunnel to great speed up effect. Instead, it's blocked up because of one dick.
The first is an iterative method while the second is a recursive method. To give you an idea, to calculate n=45, it takes the iterative method about 90 steps while the recursive method takes over a billion steps.
import os
def goodFib(num):
fibs = [1,2]
for x in range(2, num):
fibs.append(fibs[x-1] + fibs[x-2])
return fibs[num - 1]
def badFib(num):
if (num == 0 or num == 1):
return 1
else:
return badFib(num - 1) + badFib(num - 2)
def benchmark(test, value):
t1 = os.times()
print test(value)
t2 = os.times()
systemTime = t2[0] - t1[0]
print "Time elapsed: %s" % systemTime
for x in range (0, 100):
print "Good algorithm"
benchmark(goodFib, x)
print "Bad algorithm"
benchmark(badFib, x)
print "~~~~~~~~~~~~~~~~~~"
Andrew's solution of letting dwarves squeeze past each other is helpful, although if dwarves squeezing past each other still has a move penalty the complexity of the problem remains relatively high - unless you're willing to accept suboptimal solutions.
The other interesting thing about the issue is that although the globally optimal solution would be that the sum of the lengths of the paths is minimized, the locally optimal solution from each dwarf's point of view would probably involve a fight.
Here's a blog talking about porting it over to mac, but they have the source available for download.
Once again, I'm not a programmer, but I've been looking for some path finding in this code. So far I have this...
void unitst::move_randomly()
{
//IF YOU ALREADY HAVE A PATH, KEEP FOLLOWING IT
if(path_x.size()>0)
{
if(game.cave.walkable(path_x[0],path_y[0],this,1))
{
x=path_x[0];
y=path_y[0];
path_x.erase(0);
path_y.erase(0);
return;
}
}
//OTHERWISE MOVE RANDOMLY
short sx=0;
short sy=0;
if(trandom(2))sx=trandom(2)*2-1;
else sy=trandom(2)*2-1;
if(game.cave.walkable(x+sx,y+sy,this,1))
{
x=x+sx;
y=y+sy;
}
}
void unitst::move_toward(short fgx,short fgy)
{
if(gx!=fgx||gy!=fgy)
{
gx=fgx;
gy=fgy;
game.cave.buildpath(x,y,gx,gy,path_x,path_y,this);
}
if(path_x.size()>0)
{
if(game.cave.walkable(path_x[0],path_y[0],this,1))
{
x=path_x[0];
y=path_y[0];
path_x.erase(0);
path_y.erase(0);
}
}
}
Also, it looks like game.cave.buildpath holds the actual pathfinding code; what you posted just covers movement. Given the use of erase(), I hope that's a linked data structure he's using for the paths there.
inline void cavest::buildpath_squarecheck(short x,short y,short sx,short sy,
long fill,short lineplace,long &curplacelim,char &placed,unitst *un)
{
if(path_map[x][y]<path_start&&
(walkable(x,y,un,0)||
(x==sx&&y==sy)))
{
if(curplacelim<MAXLINELIM)
{
path_map[x][y]=fill;
placed=1;
line[lineplace][curplacelim][0]=x;
line[lineplace][curplacelim][1]=y;
curplacelim++;
if(curplacelim==MAXLINELIM)
{
errorlog_string("Build Path Overflow");
}
}
}
}
void cavest::buildpath(short sx,short sy,short gx,short gy,svector<short> &path_x,svector<short> &path_y,unitst *un)
{
path_x.clear();
path_y.clear();
if(sx==gx&&sy==gy)
{
errorlog_string("BUILDPATH SAME SQUARE VIOLATION");
return;
}
if(path_start>=2000000000)path_clear=1;
if(path_clear)
{
clear_path_map();
path_start=1;
path_clear=0;
}
else path_start+=5000;//Z-BUFFERING
path_map[gx][gy]=path_start;
char placed;
int pass=1;
int l,x,y;
short linecheck=0;
short lineplace=1;
long curchecklim=1,curplacelim;
line[linecheck][0][0]=gx;
line[linecheck][0][1]=gy;
long fill=path_start+1;
long maxpass=2000;
do
{
placed=0;
curplacelim=0;
for(l=0;l<curchecklim;l++)
{
x=line[linecheck][l][0];
y=line[linecheck][l][1];
if(x>0)
{
buildpath_squarecheck(x-1,y,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(x<CAVE_DIM_X-1)
{
buildpath_squarecheck(x+1,y,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(y>0)
{
buildpath_squarecheck(x,y-1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(y<CAVE_DIM_Y-1)
{
buildpath_squarecheck(x,y+1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(x>0&&y>0)
{
buildpath_squarecheck(x-1,y-1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(x<CAVE_DIM_X-1&&y>0)
{
buildpath_squarecheck(x+1,y-1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(x>0&&y<CAVE_DIM_Y-1)
{
buildpath_squarecheck(x-1,y+1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
if(x<CAVE_DIM_X-1&&y<CAVE_DIM_Y-1)
{
buildpath_squarecheck(x+1,y+1,sx,sy,fill,lineplace,curplacelim,placed,un);
}
}
if(path_map[sx][sy]>=path_start)break;
fill++;
pass++;
if(pass>maxpass)break;
linecheck=1-linecheck;
lineplace=1-lineplace;
curchecklim=curplacelim;
}while(placed);
//IF START GOT TOUCHED, FOLLOW THE PATH BACK TO GOAL
if(path_map[sx][sy]>=path_start)
{
int px=sx,py=sy;
char moved;
while(1)
{
moved=0;
switch(trandom(8))
{
case 0:
if(px>0&&!moved)
{
if(!moved&&path_map[px-1][py]<path_map[px][py]&&
path_map[px-1][py]>=path_start){px--;moved=1;}
}
break;
case 1:
if(py>0&&!moved)
{
if(!moved&&path_map[px][py-1]<path_map[px][py]&&
path_map[px][py-1]>=path_start){py--;moved=1;}
}
break;
case 2:
if(px<CAVE_DIM_X-1&&!moved)
{
if(!moved&&path_map[px+1][py]<path_map[px][py]&&
path_map[px+1][py]>=path_start){px++;moved=1;}
}
break;
case 3:
if(py<CAVE_DIM_Y-1&&!moved)
{
if(!moved&&path_map[px][py+1]<path_map[px][py]&&
path_map[px][py+1]>=path_start){py++;moved=1;}
}
break;
case 4:
if(px>0&&py>0&&!moved)
{
if(!moved&&path_map[px-1][py-1]<path_map[px][py]&&
path_map[px-1][py-1]>=path_start){px--;py--;moved=1;}
}
break;
case 5:
if(px<CAVE_DIM_X-1&&py>0&&!moved)
{
if(!moved&&path_map[px+1][py-1]<path_map[px][py]&&
path_map[px+1][py-1]>=path_start){px++;py--;moved=1;}
}
break;
case 6:
if(px>0&&py<CAVE_DIM_Y-1&&!moved)
{
if(!moved&&path_map[px-1][py+1]<path_map[px][py]&&
path_map[px-1][py+1]>=path_start){px--;py++;moved=1;}
}
break;
case 7:
if(px<CAVE_DIM_X-1&&py<CAVE_DIM_Y-1&&!moved)
{
if(!moved&&path_map[px+1][py+1]<path_map[px][py]&&
path_map[px+1][py+1]>=path_start){px++;py++;moved=1;}
}
break;
}
if(moved)
{
path_x.push_back(px);
path_y.push_back(py);
if(px==gx&&py==gy)break;
}
}
}
}
Not a good approach, overall. The way he's done the randomization only serves to slow things down, and Dijkstra's algorithm is a poor choice given the situation.
At least this isn't what's used in Dwarf Fortress.