Print

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

[numerobis]

The only reason to roll our own PRNG is for debugging: making sure the same random seed gets the same result for everyone.  It's not clear to me we'll have any randomness in the inner loop (right now, it's just to generate paths -- and that probably should be an input file anyway), so just grabbing the first one we see with a compatible license is good enough.

Oh, hey, look at this, public-domain library, fast, state of the art.  Search done: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

[Fieari]

Right now I'm fiddling with the program to get it to utilize different movement types.  Just altering the graph, pretty much, not implementing connectivity maps yet or anything.  I've only set 7 different types, and the criteria for inclusion is that each type is a positive type, not a negative type.  That is, if you have a movement type, you can positively move on any square with that allowance.  There are no squares right now that FORBID you from moving there if you DON'T have the type.

That is, if a square were WALK and MIASMA, and your movement types were WALK only, you'd be able to move through the miasma fine because it allows walkers, and the fact that you don't have miasma movement is ignored.

For testing purposes, I also only put into the map reader the ability to combine the first 4 types so I wouldn't have to muck about with binary files, keeping the maps human readable.

The only annoying part is I'm having to change just about every function to pass the integer possessing the movement types allowed by the actor.  Tracking down every spot that this is needed is a bit annoying, but it's preferable by far to using a global, and this is a fundamental enough priority of the project that it probably does need to be pervasive.

[Fieari]

Until I figure out how to use that GIT thing... here's a mediafire upload of my changes.  Note that this does include the random() to rand() change.

[Nexii Malthus]

The wow power leveling usual point where break even

happens is around 4,000 copies. If you're printing wow gold

4,000 copies of a given item, aion power leveling it's

almost always better aion gold to go to an offset press for

the job, though cheap wow power leveling this will vary

considerably buy wow power leveling by region and services

offered.When looking at the cost effectiveness aion kinah
of colour laser printing,

NNNNNNNNNNOOOOOOOOOOOOOOOOOOOOOOoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

[Sunken]

Whew, I was beginning to think this thread had died!


...or, wait, what?

[eerr]

This is dead, also, the problems with pathfinding are rather... derivative.

not a problem with one path, but rather with many simultaneous paths that must all recalculate when they intercede.

[Nadaka]

This is dead, also, the problems with pathfinding are rather... derivative.

not a problem with one path, but rather with many simultaneous paths that must all recalculate when they intercede.

probably right. The best way to optimize path finding is caching or parallelization.
Caching could improve performance for most systems, except those with limited memory.
Parallelization could improve performance for most systems, except those with a single core.

[Sunken]

Caching won't help anyone without meaningful clustering, though, as pointed out above.

[Starver]

Keyboard: 4.75->8   3.25   1.5kg
16cable:  4.75->10.75   6   2.7kg

This is dead, also, the problems with pathfinding are rather... derivative.

not a problem with one path, but rather with many simultaneous paths that must all recalculate when they intercede.

I find the announcement that this is a dead project a little premature for my taste.  The fact that different people (and even the same people, at different times, puts hand up... "Guilty!") have been discussing different aspects from those that other people consider core has made it a bit less concentrated than it perhaps could have been, but I, for one, have learnt that some of the terms I 'made up' for my own thought experiments were surprisingly similar to some that actually dedicated problem solvers had layed down in full-on published papers.  Which is gratifying to know.

While I haven't yet got involved in getting down and dirty with actual coding, I still have Plans (TM) to either get the provided platform set up at home or at least make test implementations of my own.

(Ok, so I've been busy over the last few weekends, and the few hours I had to spare this last one that I could have done something practical with I devoted to playing a bit of Oolite.  No, I've not not had much practical DF time, recently, just some theory.)

I'd boil all the discussed issues down to:

• Algorithm (A* or derivative or something novel), with or without 'multi-terrain' ability[1]
• Dynamic environment's effects on routes[2], and a little advanced speculation about alternate movement possibilities.
• Zoning/segmentation methods to streamline the routefinding methods (and the given efficiencies/inefficiences involved).
• Caching methodology (especially regarding potential sharing between at least transiently compatible movement-classes).
• An environment/engine for testing and comparing (which I really don't know enough about to comment)
• Eventually (long-term) the possibility of integrating it into a DF build.  If not the DF build.
  

...not all of which was supposed to be the be-all-and-end-all of this thread, of course.

[Post-edit rewording @Sunken: I split the caching and clustering (a.k.a. zoning/segmentation, at least the way I understand what you mean) apart from each other, above, but of course there's a link between all the above and the rest, and that one's a particular strong one.  If you don't take the approach of resolving to abstract nodes as an act of separation between 'physical' and logical so-called-reality.  Hmm, that's not explained well.  YKWIM, I hope.)

[1] Personally, I'd say popular movement classes use their own specific mono-/multi-terrain capabilities to create parts of the cached routing systems for their own class, leaving opportunities for sharing.  Any rare or minority movement class gets asked to work their own route out on-the-fly, but could still gain advantage through suitable opening/closing opportunities message-passing to the agent's routine.  Or at least potential route-closing changes.

[2] For now, I'm leaving out the concept of routing based upon an individual agent's "knowledge".  That would probably mean a completely different approach.

[CobaltKobold]

...it's "announcing". Seriously.
(c/c++ argument) ASM! 

Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.

returns bad routes if no route exists-the current problem people ha'e with "restricted" not really stopping dwarfs if it's the only way.
TASK: FETCH IRON BOOT
LOCATION: MAGMA PIPE
Urist: Hey, I found the best route at infinite cost! Let's go!
Urist has died in the heat x180
Your fortress has crumbled to its end.

Not only are rectangles the most common thing people build in DF

BAHAHAHAHAHAHHAAAAA...er, sorry.

Obviously, this makes for trouble if the traffic zones are changed a lot or are badly shaped (dots spread out in the middle of rooms and so on).

I'm not the only one who Restricts or Lows saplings when wood is a problem, or Highs valuable sand tiles.

But what about larger agents like wagons, two close trees can form an impenetrable barrier.  Their would need to be a TCZ for each agent size which will probably be prohibitive.

this is one of the main reasons Toady is off multi-tile critters atm, I believe. (Balance issues, nailing down tile size are others). Wagons are currently in because you need, basically, to check the Depot Access twice per wagon merchantgroup- plus when you hit shift-D, ne'er actively...well, I think. Prolly wrong- I hear dead pathfinding kills(scuttles) a wagon.

You can also, for example, precalculate map for next season because you know that tree saplings will become obstacles.

uh, trampling.

Alternatively you could assume everything above a 'top level' zone is a trivial connection to critters passing through these can move freely, which although means a special case is probably a cleaner solution overall.

That's a possibility, although it's not trivial to carry out in practice.
[/quote]There is a huge problem with this, namely, underworld layers. Certainly treating fliers as special case with 'Outside Light' as a connected zone (not necessarily trivially, terrain ridges an be problematic) should be worth something.

On to constructiveness.
==Path Changers==
The Good
Building completions, all sorts.
Buildings destroyed.
Mining, most sorts
Door locks
Channeling (effects may be distant pathwise from the tile it's done from Not for fliers!
The bad/moderate
Lever-action stuff (take note: bridges can cut off paths when down, too- for fliers, or by ramps)
Caveins- precipitated by a Good, can be quite a lot of changes.
NEW: Exploration
The ugly
Water flowing. (swimmers, nonswimmers. non-waterbreathing swimmers.)
Magma flowing. (magmaswimmers, the rest): Flows are also a problem, possibly in part because they affect pathing of dwarfs..tracking them's gonna be a bitch.
Water freezing.
Obsidian forming.
creatures moving (so you can avoid running into them an dhaving to go low/high) - this one is, I hear, a nasty FPS hit if you don't ha'e sufficient traffic space, as it causes them to (seek other path) and FAIL, which is slow.

it seems relatively trivial to maintain parallel route-maps for such as aerial, aquatic, magma-surviving,
[snip]
The above possibilities means multiplication 5-fold of the map (or, rather, 5 maps if better optimisation of each map can be made),

Except these features are nonexclusive! You can perfectly well have flying amphibious fireimmunes. (We don't, yet, I think). This would be able to use a path that, in theory, existed in none of the individual maps. So, maintaining each would be 2^flags. your 5x becomes 32x, which, considering the problem looked at...is nasty. And I count 8+ (okay, really 7 and a tristate, for 384x)

Also, by using a full byte, you add support for conditional blockage at a future date(8 bits per tile).

Um, we're already past 8 options
Terrain Move Abilities (starver got some, but not all, Fieari picked up on building destroyer)
surface swim
underswim
fireimmune/magmaswim (does this ha'e an underswim variation, or just one? Might want three variants for Future.)
air-breathe
fly
open-doors(ugly. Can slip by when something else does)
lockpicking
BUILDINGDESTROYER:1
BUILDINGDESTROYER:2
"outdoors"-the order
Buroughs
FUTURE/less definitely useful
Trapavoid?
jump(N)
climb
fall-acceptable
glide
avoid-plants(Keep off the live shrubs/saplings?)- could be more a weighting factor, but I can see it causing walls.
digger
LIGHT (if faultily stored atm)- think vampires
Knowledge (faction X)
miasma
steam
mist
magmamist
dust

Nasty Pathing Operations
Flows?/Pressure?
Building (potentially)- find closest up to 100 of eachstone/wood/metal/blocks! Remember distances!

[Shades]

Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.

returns bad routes if no route exists-the current problem people ha'e with "restricted" not really stopping dwarfs if it's the only way.

I said non-passable, not restricted. The point was to avoid having lots of maps by limiting zones to connection types. A critter can only pass through a whole zone or they can't at all. Some zones might be one square doing this (a single door for example). I obviously wasn't clear enough with how I explained it, never been good at that.

[CobaltKobold]

I know you said unpassable. That's why my point- you want it to return no path, not a path with infinite cost, or creatures will STILL TRY to go that (invalid!) way if nothing else is available.

Like the steel boot in the magma pipe.

[Fieari]

Terrain Move Abilities (starver got some, but not all

Not all of these should be movement types.  At least not "inclusive" movement types, where a creature can move through the tile if he has -any- of the movement options available.  But if we must add the complexity of exclusionary movement types, where the creature MUST have a movement type to move through it, we can cut down on even more.

For instance, fireimmune/magmaswim/swim. These are three good inclusive tags, but with exclusive mapping in addition to inclusive, you could drop it to just swim and fireimmune, with magmaswim being "any with swim, but exclusive to fireimmune".  You could also add in airbreath to the exclusive mix, removing the need for seperate under and surphace swim tags.

Also... what would be the point of mist as a movement type?  Or magma mist given that you already proposed fireimmune?  Why would someone avoid dust, unless you mean cave in dust, and that kind of dust isn't the sort that you path around because it's so momentary.

I still do dispute the need for a seperate BUILDINGDESTROYER:1 or 2.  I would really prefer just weighting the cost of going through different types of constructions and materials.  Moving it from a "is it possible" question to a "is it really worth the effort" question.  If you're the sort of creature that will bust through stuff to get places, the only question is how difficult busting through that stuff is.

...

But all this is assuming we use exclusionary movement types. I'm not entirely convinced that's really a good idea though, simply because it would add a lot more divisions to the connectivity map part of the calculation, but it does offer benefits, it is true.  Doors would be easier to add to the pathfinding, for instance.  But the question is-- would it add to CPU load for pathfinding?  The algorithms I have in my head suggest that yes, it would, which is why in my implementation above I use inclusive movement types only.  But if anyone has an idea on how to add exclusionary movement types without increasing CPU load, I'm all ears.

Of course, the best part of exclusionary movement would be that we could add SIZE:xx movement types, for the pathfinding benefit of multitile creatures... I dunno.  The pros and cons need to be weighed.

[numerobis]

Whether we look at one hierarchy per creature type, or one hierarchy per terrain type, it seems like we'd get a lot of hierarchies that we need to store and keep up to date.  With hierarchies, keeping things up to date shouldn't be too expensive hopefully, so really it's the space that's worrisome.  Naively, each grid element needs a pointer to a node for each hierarchy being stored.  That gets expensive fast.  It may be possible to compress this somewhat.  But that gets complicated fast.

One method, if we believe that most paths only need to use a small number of the terrain or creature types, is to treat the hierarchies as caches: so the hierarchies for kittens and for dwarves would be loaded up pretty much always, but that for dragons pretty much never, and that for goblins only when there are a lot of goblins on the map.  If we do it by terrain type, we'd choose to maintain hierarchies over terrain types that get used a lot (floors, retricted zones) and not store hierarchies for the rarely-used ones (magma, open space).

Then pathing is: if there's a hierarchy for the current creature, use it.  If not, just do A* like in olden times.  I'm not 100% clear on the multiple terrain type version of this game, but the HA* paper was playing exactly that.

[Idles]

Terrain Move Abilities (starver got some, but not all

Not all of these should be movement types.
...
But if anyone has an idea on how to add exclusionary movement types without increasing CPU load, I'm all ears.

Read the hierarchical annotated A* paper linked multiple times throughout the thread. It allows for multiple movement types and varying creature sizes. If we were to start off using that as a basis for this pathfinding project, we would want to keep the list of "movement ability" categories as small as possible in order to avoid using a lot of memory for the hierarchical pathing graphs. In that system, your abstract "high level" pathing graph takes up an amount of memory proportional to the number of movement categories you want to have. This "high level" abstract graph has far fewer nodes and edges than the low-level tile-based graph--thus, pathfinding in the "high level" graph saves you CPU cycles because the search space is far smaller.

Thus, to fit current DF movement types into categories, you'd have:
walker ("floor", "ramp", "stairs", "unlocked door" tiles with no water or magma)
flyer (walker tiles + "open space" tiles -- this maps to giant eagles)
swimmer (any tile with water level > 4 -- this maps to carp)
amphibious ( walker + swimmer -- this maps to snakemen/lungfish)
dwarf( walker + tiles with water level <= 4 + "pet-impassible doors")
magmaphibian(walker tiles (+ any magma) + "open space" tiles with magma > 4 -- this is imps, etc.)
destroyer(walker + "locked doors" + "buildings" -- this maps to trolls, dragons, etc.)
digger( walker + "wall" tiles)

Right there you've basically got 8 movement types, which fits in a byte. A creature has just a single movement type, which in turn describes all the possible tile states that the creature can move through.

I can't think of anything that doesn't fit into these categories, besides I think spirits of fire, which if I remember correctly can fly as well as swim through water and magma.

Basically, keep these movement types in mind while you read the Hierarchical Annotated A* paper and you'll have a good starting point for this pathfinder.