Print

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

[Slogo]

Pets just need to path towards their owner. There should be a parameter how close they need to be (i.e. within how many squares). A pet following the dwarf should only get through the door if the dwarf wants it to stay close, and that means stay directly adjacent.

That code can be reused for things like ducklings behind their mother, a chain gang, caravans, military formations etc. The distances that need to be pathed are very short and shouldn't pose a significant burden, while still allowing the complete flexibility to move out of the way, should there be a problem with that route.

That's starting to get beyond the scope of pathfinding though. There are some crowd and leader/follower based pathfinding optimizations which would be worth looking into but for the most part it's the goal selection that's going to make pets behave the way they do. I think some help with goal finding work may be within what we're doing I don't think we really need to modify how pets pick which tile they're going to head towards, only how they get there.

[Combatjuan]

Not sure about the boost include problem, but I had to:
#include <limit>
#include <algorithm>

and comment out one of the printfs on account of 64bitness.

This was on Ubuntu 9.04, x64.  I lack mercurial foo and made no attempt to update them.

[Silverionmox]

Yes, rooms should have multiple connections. The choice between them would be made with A*. If they are along paths with the same distance to the destination, then the choice of which door is implementation dependent.

This could be made random if in the implementation of A*, potential next-nodes are added to the priority queue such that their relative position among other nodes with the same score is random. (i.e. Find position of queue of first node with that score, and last node with that score and choose a random number between 0 and 1 + [the difference between the two positions], insert the potential next-node at position [position of first node]+[random number]).

This could be made to select for larger hallways if a secondary score consisting of the average width or minimum width of the path was used as a tie-breaker. Also the presence/absence of cats/goblins/miasma could also be used similarly. Or an heuristic taking into account all of the above could be used (anything you can describe mathematically is possible).

Assuming this situation with two cells, picking a random entrance: the yellow route is the normal one, the red route is the actual one that is taken when the water and the miasma are avoided. That leads to zigzagging if avoidance is only considered within cells. The choice of connection should be re-evaluated if taking another path is necessary, but only after half of the distance of the new part has been traversed.

[shadow_slicer]

@Silverionmox:
There are several ways to deal with the problem you are bringing up.

1) In my previous post I mentioned that if the shortest path was absolutely necessary we could add some heuristic tie-breaking rules to prefer certain paths over others. If one of the rules was to choose the path farthest from miasma/water, then it would avoid the problem depicted in the picture.

2) If the shortest path is not necessary, we could simply raise the path cost for traveling over water and miasma tiles. Then hierarchical A* would find the best path with no modifications.

I don't really see the need to re-evaluate the path after a portion of the path has been traversed. If you really need to for some reason, then the hierarchical A* should be fast enough. You could use a distance-vector based method instead. A distance-vector pathing algorithm would have the rooms record their distance to all other rooms, and a dwarf would path towards the room closest to the destination. This would be sub-optimal, but allows for incremental pathing (though it would actually be more prone the the problems you describe!)

[Impaler[WrG]]

While it's true that path caching at high abstraction levels is necessary that's not to say that lower levels wouldn't be allowed as well.  After all the abstraction hierarchy is going to have multiple levels and paths at all such levels should be possible with the lowest level match being returned for any request.

Invalidation of cached paths on map changes seems to me to be very tricky, while its possible to know that a path has been blocked by a map change theirs no way to know if the opening of a shortcut has made the path undesirable.  As was pointed out already any cache should be set up to occasionally do a confirmationary search after a hit, if the search finds a different path then the one that's in the cache it updates it.  This should allow shortcuts and blockages to be picked up rapidly.

[Slogo]

Well, in the context of dwarf fortress pathing around Miasma and shallow water seems overstepping the bounds of the pathfinding algorithms but lets assume it's not.

As a second note if the red route is more efficient than a smoother route going through the top part of the divider it should still probably be used, I don't think it would make more sense for the dwarf to go all the way around.

Disregarding that I'd handle the situation in a few ways but I need a little more time to write them out properly. Suffice to say that I don't think it'll be a major hurdle to using a hierarchy and I'm sure there's already some pre-existing algorithms to handle it.

[numerobis]

Code: [Select]

9 C:\programming\pathing\graph.h boost/iterator/iterator_facade.hpp: No such file or directory.

What version boost?  iterator_facade has been around a while, but some versions of boost out there are *ancient*.

#include <limit>
#include <algorithm>
and comment out one of the printfs on account of 64bitness.

Which file needs those includes?  And which printf?  All the printfs are printing either unsigned with a %u format, or uint64_t with a %llu format, so those should be clean -- they compile 32 or 64 bit on my machine, but I recognize these things differ across platforms.

[Nexii Malthus]

I'd go for the artificial stupidity that the red path brings.

I think that attempting to implement behavioural quirks in pathfinding is a good thought but might be far beyond technical limits. [Regarding avoiding miasma specifically]

[Sunken]

Miasma avoidance can be handled by an automatic traffic cost setting, so any scheme that can deal with traffic costs can deal with that, in principle. (Though its dynamic nature may prove troublesome.)

[Impaler[WrG]]

Traffic costs dose make me think how were going to combine that with movement types, a flying creature should have the same cost at all time ware as a walking creature would be slowed down by mud and other unfavorable conditions.  Each movement type might require its own cost which may present a significant memory overhead.

[Fieari]

I found out what was causing that particular error, and it was using the makefile you included.  Don't know why that screwed it up, but it might be that I'm compiling in windows, even if I am still using gcc.

Now that I've removed the makefile, I'm down to just one error.

Code: [Select]

C:\programming\pathing\main.cpp In function `point randomPassablePoint(const grid*)':

16 C:\programming\pathing\main.cpp `random' undeclared (first use this function)
If you change random() to rand(), it compiles runs and works.  Now just to see how it works and tinker away on my day off...

[Slogo]

Traffic costs dose make me think how were going to combine that with movement types, a flying creature should have the same cost at all time ware as a walking creature would be slowed down by mud and other unfavorable conditions.  Each movement type might require its own cost which may present a significant memory overhead.

If you sum up the movement cost of a tile on demand you could also add some sort of ignore flag to just skip these types of factors.

[numerobis]

If you change random() to rand(), it compiles runs and works.  Now just to see how it works and tinker away on my day off...

Ugh.  I haven't suffered from the lack of random() in about 10 years.  In real code we'd probably end up rolling our own PRNG, but the real lesson is that cross-platform stuff like this bites.  Maybe I'll set up automake this weekend, which should help a bit. 

My weekend goal: add in a graph sparsifier along the lines of what I mentioned, and hierarchical A* based on that (we can do different sparsifiers later, like the one in the ualberta paper).  And make things more cross-platform-safe.

[Fieari]

You know, I remember a thread a while back where someone demonstrated that the pRNG that Toady was using was pretty sub-par, and how instead of generating millions of different worlds, it actually only generated a much smaller number with a lot of repeating, and he wanted him to replace the code.  So it might not be a bad idea to implement our own pRNG anyway for that reason alone.

Been looking up some options, and I think the Mersenne twister is too slow for our needs.  Perhaps the MWC method would be better?

Anyway, another thing I've never used but would probably be helpful would be a CVS repository. Shall we set something up at sourceforge?

[numerobis]

I'm currently trying to figure out github...  It seems like I might have done something with http://github.com/numerobis/dwarf-path