Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: [1] 2 3

Author Topic: Burrows and pathfinding  (Read 4494 times)

Duke 2.0

  • Bay Watcher
  • [CONQUISTADOR:BIRD]
    • View Profile
Burrows and pathfinding
« on: July 02, 2009, 11:17:34 pm »

 Alright, so we know one of the greatest resource drains in DF is pathfinding. The method used simply floods the map, looking for a path to where one's job is. With the advent of burrows in the next version, many dwarves will basically be restricted to where they work, where they live and where they eat/drink. My suggestion is that if a job is located in the same burrow as the dwarf to take it, the pathfinding flood will not leave the burrow zone.

 Now what if a job is outside the burrow? Then the system makes a simple check if the job is inside the burrow or not, and make the pathfinding adjustment then. What if one needs to travel outside the burrow to reach the job, such as a burrow split in half by a wall? Then if the pathfinding fails then it will start look outside the burrow for a path.

 Basically, if one has a large forge burrow with various entrances to different parts of the fortress, dwarves will not look down these paths for a job the game knows is inside the burrow, and not down these halls.
Logged
Buck up friendo, we're all on the level here.
I would bet money Andrew has edited things retroactively, except I can't prove anything because it was edited retroactively.
MIERDO MILLAS DE VIBORAS FURIOSAS PARA ESTRANGULARTE MUERTO

Silverionmox

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #1 on: July 03, 2009, 03:39:55 am »

My impression was that dwarves don't do stuff outside their burrow. It's even better to check whether something is in the relevant burrow (yes/no) before determining whether the dwarf gets the job.
« Last Edit: July 03, 2009, 03:41:26 am by Silverionmox »
Logged
Dwarf Fortress cured my savescumming.

Felblood

  • Bay Watcher
  • No, you don't.
    • View Profile
Re: Burrows and pathfinding
« Reply #2 on: July 03, 2009, 11:30:52 am »

I believe some burrow settings will be less restrictive than others, so some will only force dwarves to work in the burrow, while still allowing them to eat from the general stockpiles outside.

If a dwarf tries to path to a destination in his burrow and fails, he should resume flooding from his borrow only flood, instead of starting over from square one. This might occasionally cost us a tiny bit of memory, but it should conserve CPU time on a regular basis.
Logged
The path through the wilderness is rarely direct. Reaching the destination is useless,
if you don't learn the lessons of the dessert.
--but you do have to keep walking.

Duke 2.0

  • Bay Watcher
  • [CONQUISTADOR:BIRD]
    • View Profile
Re: Burrows and pathfinding
« Reply #3 on: July 03, 2009, 12:49:16 pm »

My impression was that dwarves don't do stuff outside their burrow. It's even better to check whether something is in the relevant burrow (yes/no) before determining whether the dwarf gets the job.
From what I understand Toady was going to allow a lot of ways a dwarf can go outside a burrow, because there are many situations where invisible walls won't stop a dwarf. This is just a suggestion to limit the pathfinding code if the right conditions are met. But yes, dwarves should only really get jobs from inside their burrow. That feature seems a bit more implied than limiting pathfinding, though.
Logged
Buck up friendo, we're all on the level here.
I would bet money Andrew has edited things retroactively, except I can't prove anything because it was edited retroactively.
MIERDO MILLAS DE VIBORAS FURIOSAS PARA ESTRANGULARTE MUERTO

Silverionmox

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #4 on: July 03, 2009, 01:36:28 pm »

If I'm not mistaken, they just do stuff inside their burrow (including milling around bored if there are no jobs), but not to the point of starving themselves etc.
Logged
Dwarf Fortress cured my savescumming.

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #5 on: July 03, 2009, 04:56:31 pm »

I was about to write a derisive reply to a post in this thread but decided to check things out before opening my big mouth.
Where can I find the authoritative word on how pathing works in DF? The Wiki article is very barebone. I know there are people on here who know a great deal; is there a source for this knowledge somewhere?
Logged
Alpha version? More like elf aversion!

Duke 2.0

  • Bay Watcher
  • [CONQUISTADOR:BIRD]
    • View Profile
Re: Burrows and pathfinding
« Reply #6 on: July 03, 2009, 07:27:28 pm »

 There was a gamasutra article that had an interview with Toady, so I'll post the link to it.
 Ten pages of Goodness.

 But yes, from what I understand a dwarf will generally just stay inside their burrow. My suggestion is to limit the pathfinding flood which would otherwise check outside the burrow despite the restriction of where the item can be. Although this topic might be a bit premature, as we don't even know if Toady has this in yet or not.
« Last Edit: July 03, 2009, 07:33:55 pm by Duke 2.0 »
Logged
Buck up friendo, we're all on the level here.
I would bet money Andrew has edited things retroactively, except I can't prove anything because it was edited retroactively.
MIERDO MILLAS DE VIBORAS FURIOSAS PARA ESTRANGULARTE MUERTO

Fieari

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #7 on: July 04, 2009, 10:13:35 pm »

Actually, the pathfinder DOESN'T flood the map.  It uses the A* algorithm, which you can read about in most computer science textbooks, or discrete mathematics textbooks.  It's related to Dijkstra's algorithm.  You're thinking of the connectivity map, which does use flood fill.  Using burrows to restrict the connectivity map would be a bad idea.
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #8 on: July 05, 2009, 12:10:33 pm »

Actually, the pathfinder DOESN'T flood the map.  It uses the A* algorithm, which you can read about in most computer science textbooks, or discrete mathematics textbooks.  It's related to Dijkstra's algorithm.  You're thinking of the connectivity map, which does use flood fill.  Using burrows to restrict the connectivity map would be a bad idea.

As you'd need one for every burrow (as they CAN OVERLAP), plus a full map one for things that ignore burrows.
Logged

SwiftAusterity

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #9 on: July 05, 2009, 12:30:31 pm »

One thing that burrows could solve is if you cached pathing for particular burrow + path instead of regenerating them every time you needed pathing for something.

The scope of such a caching system would be enormous and possibly worse than not caching depending on your running environment.

AI Track (hunting, goal attainment) pathing in my old MUD was based on A*, and the entire thing was a giant cache system whereby entities would "remember" how to get places (after having been there) and form quasi-patrol routes for goal attainment.

Instead of generating a new path on the base algorithm it'd search its current paths for a drop point (current location = on the path somewhere) and execute the path from there to finish. Drop point searching proved faster (in a majority of cases) and gave a sense of "memory" to behavioral patterns.

Granted, I've no idea how the system here is coded so it's pure speculation as to what would work ;)

EDIT: The main idea of caching it per burrow is a lot less like faked memory as well, because it'd only work if all dwarves shared a hive mind about paths they've taken inside a burrow.
« Last Edit: July 05, 2009, 12:33:08 pm by SwiftAusterity »
Logged

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #10 on: July 06, 2009, 09:05:03 am »

What we really need is a required reading FAQ on pathfinding, so people understand the issues that DF poses.

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #11 on: July 06, 2009, 01:44:40 pm »

Second that! Who will write it?
Logged
Alpha version? More like elf aversion!

Granite26

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #12 on: July 06, 2009, 01:52:30 pm »

Done

Edit:  Er... I get cranky when I don't get enough sleep.  There are quite a few really good discussions about what pathfinding actually does and why flowing water and lava and digging and flying and traffic and path costs and climbing and doors and floodgates play hell with any sort of caching solution.  Draco18s is usually knee-deep in explaining them.
« Last Edit: July 06, 2009, 01:56:21 pm by Granite26 »
Logged

Fieari

  • Bay Watcher
    • View Profile
Re: Burrows and pathfinding
« Reply #13 on: July 06, 2009, 02:25:57 pm »

I don't know if my suggestion on improving the system would help in explaining it... it's a lot of compsci, using bitwise arithmatic and big O theory (and my suggestion isn't for an improvement in speed, it's for an improvement in accuracy).  But it does cover the basics.

I think that people hear "the pathfinding is slowing the system down" and then instantly try to figure out what the pathfinding system might be doing in their heads, causing them to mentally write their own interpretation of how to make a pathfinding system work at all, and assume that's what needs to be done.
Logged

Sunken

  • Bay Watcher
  • Wabewalker
    • View Profile
Re: Burrows and pathfinding
« Reply #14 on: July 06, 2009, 02:42:48 pm »

What I want to know is what's been considered (or already implemented!) in terms of intelligent segmentation of space into larger units. I know that there are "connected components", but as far as I've understood it they are simply the result of flood-filling as far as it will go, meaning that in general they will be very few and very large; is that correct?

I'm (professionally) interested in intelligent abstraction of space so I'd welcome a FAQ that discusses it as pertains to DF. Personally I think that some heuristic segmentation should be able both to allow pathfinding to scale better (and to permit fancier AI, like in Fieari's thread) and be suboptimal only in inoffensive ways - perhaps making dwarfs more "human" in the way they move about.
Logged
Alpha version? More like elf aversion!
Pages: [1] 2 3