Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Impaler[WrG]]

Interesting work, are you interested in integrating what you have so far with Khazad or are you ok with me trying to do so myself.  I've downloaded your code and it looks like it should be simple to convert from the test maps to using extracted fortress data out of khazad.

[shadow_slicer]

I think it would probably be better for you to do it yourself. To add the path finding code in all you should need to do is create a class that implements gridInterface and understands how Khazad stores map data. I haven't looked at Khazad that much, so it would probably be more difficult for me to figure it out.

[eerr]

The problem with pathfinding is multiple creatures.

Toady has the code set to recalculate pathfinding for every creature that paths through a tile.

can you find a more efficient method?

[PermanentInk]

Of course, we're dealing with globally-omniscient agents.  Given that we have these[1] and not limited-knowledge agents with[2] or without[3] communicative learning, Stigmergy isn't relevent to the current situation, though I know it would be an interesting thing to put into the world simulation.  With associated change of game balance.

Just because we're not constrained to a limited-knowledge approach doesn't mean we can't use one.  Consulting a global knowledge bank costs cycles, more so the larger it is.  An effective limited-knowledge technique, of which stigmergy is a good and intriguing example, can be more efficient by structurally ignoring parts of the knowledge bank not likely to be relevant to an agent's decision.

Anyway, it's not so much a question of "what we have," if you mean the current pathfinder, because the point is to rip it out and replace it with something better.  There's nothing inherently globally omniscient about DF critters; it's just a question of them being programmed that way or not.

[1] "Oh, I feel sad.  I need to speak to the Mayor.  He's deep in the caverns and I will now calculate how to get to him, and recalculate arbitrarily to his new position he moves around, despite being way beyond my vision or hearing."

[2] "Hoi!  Freind McMiner, I have been tasked to cut some fine amethyst, and I understand that you can tell me down which long tunnel they may be found...  Pray tell me, good sir, which way hither?"

[3] "Where is that log?  Where is that log?  I've been asked to get a log, and I don't know where it is.  It wasn't to the east of this wall last time I looked, but is it there now....  No, first I'll check the northern forests.  It may be there..."

I like your examples, though.  They illustrate an idea that keeps nagging at me the more of this thread I read, which is that it's not necessarily appropriate for dwarves to be omniscient.  Aren't there all kinds of interesting story possibilities that point toward pathing based on individual entity knowledge?

• You awaken bloodied and sore amid a corpse-strewn battlefield.  Rubbing a massive lump on the back of your head, you wonder where the hell you are and how to get home.
• The road is blocked ahead by a rockslide, but the caravan doesn't know that.  The bandits, however, do; they close in from behind for an ambush at the dead end.
• Only the ancient vizier knows of the secret passage behind the throne room.  That is, until one day a cleaning dwarf trips on the lever that opens the door, and his curiosity gets the better of him...

Obviously, these are pretty rich examples of such a system compared to what the game's capable of today, but the point is that any pathfinder that's going to be viable long-term should be consistent with the long-term direction of the game.

btw, I believe you mean "thither," not "hither."  "Hither and thither" is like "here and there," and I believe the usage parallels this in general.  TMYK

[shadow_slicer]

Just because we're not constrained to a limited-knowledge approach doesn't mean we can't use one.  Consulting a global knowledge bank costs cycles, more so the larger it is.  An effective limited-knowledge technique, of which stigmergy is a good and intriguing example, can be more efficient by structurally ignoring parts of the knowledge bank not likely to be relevant to an agent's decision.

That's not really true. It is significantly simpler (and faster) to solve problems using global knowledge. Any problem that can be solved with limited information can be solved at least as fast (and in the vast majority of cases faster and better) using global information. This is one of the central ideas of information theory. Techniques such as stigmergy are useful when the problem MUST be solved in a distributed manner. They are slow to converge and require significantly more overhead.

Anyway, it's not so much a question of "what we have," if you mean the current pathfinder, because the point is to rip it out and replace it with something better.  There's nothing inherently globally omniscient about DF critters; it's just a question of them being programmed that way or not.

But there is a significant difference between the kind of AI you're suggesting and pathfinding. Pathfinding really doesn't care where the knowledge comes from or how it is used. What you're talking about is AI.

[Nexii Malthus]

I have to agree with shadow_slicer, but with PermanentInk too.

The problem is that pathfinding pretty much is one of the core heart pieces of artificial intelligence, it is about finding a preferred path, where to go, where to move, how to get there, and why that path.

I do feel that Stigmergy is incredibly Awesome, and will be perfect for the dwarf swarm intelligence.

But I feel that the global information pathfinding should still be -the- underlying foundation for now, I just have a bad instinctive feeling about going fully with stigmergy. Stigmergy is a big, big job and inevitable goal. But the omniscient system will have to do for now, after all, what we are seeking is pure, liquid, clean performance. Once we have that, we can build on it.

[zchris13]

PURE CLEAN LIQUID PERFORMANCE.  WHAT A GREAT AD.

[shadow_slicer]

The problem is that pathfinding pretty much is one of the core heart pieces of artificial intelligence, it is about finding a preferred path, where to go, where to move, how to get there, and why that path.

This is probably where our difference of opinion comes from. I see pathfinding as finding the lowest cost path on an arbitrary graph. This is a mathematical property of the graph and has nothing really to do with AI. The AI determines where to go, and by defining the costs for going different routes, defines the graph. The costs themselves define "why" that route. If a dwarf is operating under limited information, some tiles could be "unexplored". These would have some default cost (a relatively high "exploration cost"). In essence all aspects of AI you want to include are simply found through defining an appropriate cost function.

I do feel that Stigmergy is incredibly Awesome, and will be perfect for the dwarf swarm intelligence.

I actually disagree about this. I think there are significantly easier ways to achieve the effects you want to achieve. Stigmergy is complicated and poorly understood. It makes sense if you want to build cheap, simple hardware to perform complex distributed tasks, but not when you're using a single powerful processor with global information on a centralized task.

[PencilinHand]

I am inclined to agree with the way shadow_slicer thinks regarding finding a computationally cheap and mathematically optimal path before anything else.

--------

If I have read and understood this thread right, the code that is being thrown around right now just arbitrarily divides a map along groupings of Cartesian coordinates forming a hierarchical system.  Then what would be most useful(for a pathfinding dwarf) would be a system of methods for more objective/less arbitrary grouping within the hierarchy.

Using the example given on the previous page, if "|" and "_" were borders for different zones at a mid level in a hierarchy of zones then something like the following might be more effective than arbitrary division.

Code: [Select]

############################
#c    ######################
#     #####  |   ###########
#    |       |    ##########
#######      |     #########
#######______|_____#########
#######     #|     |       b
#######  #   |_#############
########   # #   ###########
#########   _   ############
############ ###############
############a###############
Assuming my understanding is correct then what is really needed are efficient algorithms for forming and maintaining these zones intelligently so as to minimize path calculations from a to both b and c.

Am I way off base or is that basically the crux of the problem?

[Impaler[WrG]]

Shadowslicer: I see theirs are some boost dependencies in your code, I tend to avoid boost because its so interconnected and interdependent its nearly impossible to use in a targeted and efficient way and I'd need to include several MB of additional files in the Khazad checkout (I want it to always be compilable without any dependencies).  Do you think any of these boost dependencies can be eliminated?

[SmileyMan]

The Boost License is pretty permissive, so you should just be able to copy the Boost parts wholesale into the project without any problems (they require you to keep the copyright notice in the source files, but not in the executable).

Especially if it's one of the header-only files, I'd do that, especially as a few of them are slated to end up in C++0x anyway.

Personally, I couldn't program without the boost smart pointers anymore.

[Starver]

[2] "Hoi!  Freind McMiner, I have been tasked to cut some fine amethyst, and I understand that you can tell me down which long tunnel they may be found...  Pray tell me, good sir, which way hither?"

btw, I believe you mean "thither," not "hither."  "Hither and thither" is like "here and there," and I believe the usage parallels this in general.  TMYK

Well, "which way thither" would be a valid way of "which way to get there", but I'm sure I was writing something more like "which way from here".  So "...which way, hither?"

But that's not a pathfinding point.  (Well, not algorithmically, only contextually.   And, besides, I misspelt/misgrammared various other parts of that post ("Freind"?  Sheesh!)

[SmileyMan]

hither is "to this place (here)", and thither is "to that place (there)"  Possible also relevant is whither - "to which place?" and whence - "from which place?"

Archaic English, but possibly useful as OO method names!

[Impaler[WrG]]

Yes I know boost has some very sexy stuff and people have told me the smart pointers are great at preventing memory leaks.  But trying to include one header file requires 3 others which in turn require 3 more etc etc.  By the time your done you need the whole darn boost library which is 44 MB! (with an M) of header files and I'm not going to require people to check that out from the SVN repository its just too big.  I really wish they had some kind of boost-lite or boost-A-la-carte so you could get just the functionality you need.

I'm going to try to modify slicer's code to eliminate the boost dependencies, possibly implementing some simplified versions of the boost classes that were used.

[shadow_slicer]

The easily removed dependency in the code is boost::shared_ptr which could/should be replaced by std::shared_ptr and #include <boost/shared_ptr.hpp> by #include <memory>(since they are really the same). There are a few other data structures (unordered_set, unordered_map) that I use that were originally in boost, but (at least on my system) they are also part of the standard library.

As for the iterator in graph.h, I think it's not used in STL containers, so it might not be as difficult as I initially feared. You can simply remove the boost stuff completely and add operator++(), and operator*(), which call the existing functions. (I've done it and posted it here).

I'm currently still looking over my code. There are a couple more optimizations to the caching I could do: 1) when a path is cached, the reverse path is also cached, 2) when a path cannot be found, all nodes in the region that haven't been visited yet also are disconnected (so we can cache them as well), 3) when a path cannot be found, A* has calculated (or at least done 99% of the work necessary to calculate) the minimum path to all nodes in the region searched, so we should cache this information. I think (1) may be working in my newest version, but (2) and (3) are doing really weird things. I'm going to keep working at it. The public interfaces should stay the same, so any changes I make shouldn't make a large impact.

Edit (instead of double replying):
@PencilinHand: Yes, that is now where we stand. We were talking earlier about TCZs and other zone types. Once Impaler[WrG] has combined the code with Khazad we will have both some pathfinding code to work with and a set of realistic scenarios. Then we can all implement our zone ideas and see how they actually perform, instead of just arguing back and forth.