Bay 12 Games Forum

Please login or register.

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

Author Topic: Improving Pathfinding. (Computer sciency)  (Read 50207 times)

Draco18s

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #15 on: January 31, 2011, 07:39:47 pm »

But even with the a* algorithm, you could have a node in every second square instead of every single square. That would be faster whatever algorithm you use.

Please....please....please actually read the arguments as to why that is a bad idea.
Logged

sockless

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #16 on: January 31, 2011, 07:57:48 pm »

Well you would still be able to move orthogonally, but it will be able to assume that there's a walkable space between 2 connected nodes.
The point about the sword is an interesting one, but right now the dwarf would just look at the nearest as-the-ghost-flies distance and decide to pick up that sword, so with sparser nodes, that wouldn't be affected, it would be the same as if you were pathing to a lever. It would just grab the swords co-ords, then randomly choose a pathable space next to it. Then the dwarf would path to that square, then walk the one square different.
Logged
Iv seen people who haven't had a redheaded person in their family for quite a while, and then out of nowhere two out of three of their children have red hair.
What color was the mailman's hair?

Draco18s

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #17 on: January 31, 2011, 08:09:34 pm »

Well you would still be able to move orthogonally, but it will be able to assume that there's a walkable space between 2 connected nodes.

So now not are you storing nodes, your storing node connections, rather than being able to infer connections because the two nodes are neighboring.
Logged

Max White

  • Bay Watcher
  • Still not hollowed!
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #18 on: January 31, 2011, 08:11:45 pm »

Dosn't the great Toady one himself have degrees in mathamatics, or softwere or something of that nature? I mean I'm sure he has given this plenty of thought.

sockless

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #19 on: January 31, 2011, 08:43:45 pm »

Yes that is what I'm doing, so you build a graph at the start of the game, then as you mine stuff, it adds it to the graph.
Logged
Iv seen people who haven't had a redheaded person in their family for quite a while, and then out of nowhere two out of three of their children have red hair.
What color was the mailman's hair?

thijser

  • Bay Watcher
  • You to cut down a tree in order to make an axe!
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #20 on: February 01, 2011, 12:49:28 am »

Of course a third methode for pathing past obstacles is that whenever the computer finds a obstacle it will start to try path next to it. That way it won't have to store as much data.
Logged
I'm not a native English speaker. Feel free to point out grammar/spelling mistakes. This way I can learn better English.

Silverionmox

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #21 on: February 01, 2011, 02:04:09 pm »

Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.

- Dwarves could pathfind within burrows first, as that is the most likely place to find stuff. Animals could do something similar, at least the territorial ones. Cows/sheep should path to the leading bull/ram of the herd, but don't need much else.
- Dwarves could store frequently used paths, such as from their bedroom to the first high traffic zone (probably a staircase or important connecting corridor). It would be great if the computer could detect central staircases and prefer them for pathfinding.
- Dwarves performing routine tasks should use the above. If something pulls them out of their routine, they could revert to the ordinary, more flexible pathfinding. Adventurer mode will have townsfolk perform routine tasks anyway, so the same code can be reused.
Logged
Dwarf Fortress cured my savescumming.

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #22 on: February 01, 2011, 02:17:15 pm »

Wouldn't storing pathfinding results for "most common paths" lead to a massive consumption of memory, though?  Not that having an ability to trade processor time for memory space is a bad thing, but it can potentially exchange one problem for another if you have enough creatures walking around the map.

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.  You could even store the pathfinding from workshop to stockpile and back, which I'm sure is THE most frequent pathfinding function you perform.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

tps12

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #23 on: February 01, 2011, 03:08:12 pm »

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.

I don't think the game paths to each item in that case. It finds the closest item by Cartesian distance and then paths to that one only.
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #24 on: February 01, 2011, 03:10:15 pm »

Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.

It's a computer program.  Computers can't generalize, at all, ever.  They must perform the repetitive, excessive detail, tasks every time because that's how computers work.  The only way to skip code is to be less accurate or find some way to infer the data without looking at it (i.e. a process that takes less cycles but comes to the same result, such as "that tile is a food stockpile tile" skipping the check that asks if each item in that tile is a stone or not*).

*There could be a stone in that tile, but odds are there isn't.
« Last Edit: February 01, 2011, 03:12:55 pm by Draco18s »
Logged

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #25 on: February 01, 2011, 03:12:18 pm »

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.

I don't think the game paths to each item in that case. It finds the closest item by Cartesian distance and then paths to that one only.

I know, but that's not the main reason why the game lags, the game lags because every time a stonecrafter at a workshop wants to find something, he has to access a list of every single stone in the fort to then test cartesian distance of each one to find the closest, even if there are tens of thousands of stones to choose from.

If you were restricting the dwarf to searching only the contents of a single stockpile first, then only searching the rest of the entire fortress if he couldn't find what he needed in the stockpile, then you could potentially trim that list of search targets down by quite a bit, and improve overall speed.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

Nadaka

  • Bay Watcher
    • View Profile
    • http://www.nadaka.us
Re: Improving Pathfinding. (Computer sciency)
« Reply #26 on: February 01, 2011, 03:15:10 pm »

every square is a node, it isn't stored as a graph though. It is stored as an array of node entry costs IIRC. Connectivity between nodes is implicit from adjacency.

Its been a while since I got in on one of these pathfinding discussions.

IIRC the path from unit to goal is recalculated at every step, if each unit stored its current path you would cut path finding costs by a factor approximately equivalent to half the length of the average path divided by the frequency that a path becomes invalid. You could check each step to make sure the path is valid and still get a significant boost, or follow the path until it becomes immediately obstructed and save even more time. This does cost some memory, but isn't likely to be significant.

Cutting the number of nodes by 4 is only a linear speadup, comes with some abstraction issues and won't save on memory. It is the same reason that parallel path processing isn't going to be that useful, the average cpu count right now is close to 2.
Logged
Take me out to the black, tell them I ain't comin' back...
I don't care cause I'm still free, you can't take the sky from me...

I turned myself into a monster, to fight against the monsters of the world.

Draco18s

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #27 on: February 01, 2011, 03:18:20 pm »

every square is a node, it isn't stored as a graph though. It is stored as an array of node entry costs IIRC. Connectivity between nodes is implicit from adjacency.

Precisely my earlier point.
Logged

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #28 on: February 01, 2011, 03:21:26 pm »

The path isn't recalculated with every step.  You can test this to a degree by placing obstacles in the way of a dwarf who has already on deciding to go somewhere.  Locking a door in front of a dwarf when he is intent on going somewhere, like, say, to pick up a sock from a dwarf who died in a goblin ambush, will cause him to smack head-first into the door before he realizes it is now locked (or try to walk into deep water before he realizes his path has flooded), and then try to find a way to path around the obstacle the dwarf now suddenly realizes is in the way.

edit: In fact, when they realize a path is blocked, they will stand still for a while and flash a "?" sign to signify they just walked face-first into a locked door.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

Jacob/Lee

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #29 on: February 01, 2011, 03:33:49 pm »

There was a whole topic on the pathfinding algorithm some time ago.
Pages: 1 [2] 3 4 ... 26