Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 40 41 [42] 43

Author Topic: Anouncing The PathFinder Project  (Read 96288 times)

Dark_Tundra

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #615 on: March 30, 2010, 09:25:40 am »

I have little understanding of pathfinding, so ignore this if it is just insanity.


I think a node graph of landmarks sounds like a good idea, especially if the graph contains distances, (perhaps checked one at a time?) and can reduce the search area.

The dwarfs would then have a rough idea of how to get where they are going and only need to do fine pathing between one node at a time.

If a dwarf then needs to get to an object on another floor; they could path to the stairs, knowing that they would eventually get to the object, even though they havent calculated a path all the way yet.

Then if an A→B→C path is the same , or a better fit than an A→C path, the A→C path could perhaps be culled.(there isn't really any point I can see for doubling up with a shortcut that takes more time)

Assuming this was used, I'd suggest stairs and doors as landmarks, for and landmarks be grouped when possible, a row of ramps could be one long ramp rather than several choosable ramps.


I apologise if this has already been covered, though I have read the thread, I don't understand everything that is talked about. (Exept that multithreading in no way improves pathfinding algorithms, which is the whole point of this project.)
Logged

ilsadir

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #616 on: April 06, 2010, 08:06:59 pm »

Just replying to the person above trying to explain how bridging/tunneling/etc. might work...

All of these methods are simply additional connections in the pathfinding search space.  If you can bridge a gap, then the otherwise impassable 'air' tile next to a ground tile is accessible.  If you can only bridge in straight lines, the second 'air' tile is free, but after that the line is set.  If you can only bridge X tiles, after X, air-tiles are impassable.

The trick is just getting the cost correct.
Logged

Starver

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #617 on: April 07, 2010, 07:26:17 am »

If you can only bridge in straight lines, the second 'air' tile is free, but after that the line is set.
As long as no supports exist to allow a new-bridge.  (Although maybe weighted preference should be to a few longer bridges (with less dense material needs per distance) zig-zagging around an awkward gap, rather than single/double bridge-tiles being built hugging the wall and taking roughly 1:1 material:distance to do so...  Really that needs a picture to explain properly.)

Quote
If you can only bridge X tiles, after X, air-tiles are impassable.
And in two ways:
  • The actual inability to create bridges of >10 length (save by connecting two end-supported <=10 bridges together to bridge a gap of 20, of course).  This would be an upper limit.
  • Materials available.  But if materials can be harvested, then this might just be a weighting against, and associated with tasking an allied/squad-attached axe-unit to go and chop down a couple more trees.

Quote
The trick is just getting the cost correct.
Agreed.  Utterly.

(Might be simpler to allow siege units to have at hand a certain number of specific-length hurdles/ladders/rope bridges, upon spawning, and limit them to that, and one bridging-item per given allowable bridging length, non-reusably.  Unless and until the AI can handle tree felling or rock mining than architecturally designing bridges or otherwise constructing their access points from locally obtained materials with a degree of sanity.  Actually, I like the idea of rope bridges (or at least ropes).  That would solve the whole idea of double-bridging, because you'd need to have them capable of throwing and grappling/pitoning one end of the rope onto the other side of the gap (or on top of the wall they wish to ascend), and it could even be considered a pathway only available to trained siege troops (maybe not even all units within a sieging squad) and so could leave awkward enemy-accessible routes all over the place without necessarily adding to the Fortress's own normal entrance and exit plan, to be 'cleaned up' a bit like a more resilient spider's web)...  Maybe even add skill "climbing (rope)" and/or similar, as a military thing...  Sorry, getting overly speculative there.  Ignore most of that. :))
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #618 on: April 07, 2010, 08:15:29 am »

If you can only bridge X tiles, after X, air-tiles are impassable.

How would that work?  If you can only bridge 2 tiles, max then where does the pathfinder put its bridge?


###########
#+++2+++++#
#+#+#####+#
#+#+##++++#
#+#+##+####
#+#+##++++#
#+#+##3##+#
#+#+##++++#
#+#+##+####
S+1+45++++E
###+##+####
###+##++++#
###+#####+#
###+##++++#
###+##+####
###+##++++#
###+#####+#
###+++++++#
###########


If the pathfinder puts the first bridge at that 1 tile pit (#1) then it can't skip the 2 tile pit (#4, #5) for extra-short path.

And if it bridges #2, it still can't get across #45, but could skip over #3 (shorter than bridge over #1).

But if it skips over #1 and #2 and builds a bridge over #4 and #5, then it gets the shortest path.

Finding where to build your bridge is a non-trivial problem.
Logged

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #619 on: April 07, 2010, 08:29:12 am »

Finding where to build your bridge is a non-trivial problem.

You just treat all air in a straight line as passable. It's a trivial problem assuming an algorithm such as A*, it just increases the size of the search space. Obvious cost for bridge squares are higher but that is just a detail. Digging means treating every square a passable which again increases the search space assuming the cost is higher than walking. (if the cost is the same as walking then the quickest path is a straight line)

Edit: Just realised you might have meant for the two square task, in which case it's similar but with limited air squares allowed, still fairly trivial.

If you meant the best location based on player defences then it becomes non-trivial.
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd

tylor

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #620 on: April 07, 2010, 09:37:10 am »

Invaders can have unlimited resources and cheat (like. they don't eat). So they can settle to sub-optimal path, or even sub-sub-sub-optimal. As long as they eventually can get to jucy dorf meat, it's ok.

Thay can have unlimited nomber of rock on them? pick and masonry/mining skills each and just build floors and dig rock as they go. If thay die in numbers (to magma or some other trick) they can just mark that place as (too dangerous to be around) and try to dig to fortress entrails from some other side.

Only thing that can't be passed without some very obvious cheating, I think, is lava or deep water.
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #621 on: April 07, 2010, 09:43:00 am »

Finding where to build your bridge is a non-trivial problem.
Edit: Just realised you might have meant for the two square task, in which case it's similar but with limited air squares allowed, still fairly trivial.

I'd have to see an implementation.
Logged

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #622 on: April 07, 2010, 09:54:25 am »

Edit: Just realised you might have meant for the two square task, in which case it's similar but with limited air squares allowed, still fairly trivial.

I'd have to see an implementation.
[/quote]

As well as the cost to a given square you'd need cost to a square for each size of bridge (assuming it's less than a smaller length bridge). The route itself would use it's current bridge cost when picking the next shortest path to check and seeing if the air square is passable or not.

Effectively this makes every air square within X from a land square potentially passable and so potentially on the network to path. There is no real complexity here at all as we are already checking cost to square as part of the A* search, we don't care if a square is sometimes passable and sometimes not all we care about is the current cost.
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd

Starver

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #623 on: April 07, 2010, 10:30:09 am »

With one type of pathing (a 'trivial' path, never dealing with 'consumable' path-aids) then if the pathing algorithm ever lands on a pathable square that has already been pathed to[1] then it can usually switch to the new source path if that was quicker[2].

But when bridges may or may not be made, I've already mused that you'd need to end up with a duplication of the possible pathing tree of some kind.  A 'simple' method would be to keep the "zero bridging used" map much the same as your current standard one, with a subset of that map duplicated (on a per-node basis, thus not necessarily duplicating in a huge dumb array) for every relevent position that has a zero-bridging distance[3] and a non-zero bridging access with a lower path cost than all less-bridge routes to get there.

Initially, this would need some propagation of the new duplication of node details along existing paths (though it would essentially be making use of 'cached' pathing formthe previously explored routes along the path-tendrils already explored, so would be far less 'blind' in its search than the original exploration) but once it reached the pathing 'coal face', the usual ongoing feeling around for paths could continue with not just "it cost <foo> to get here, therefore try <foo+1> on any neighbours" but "it cost <foo> to get here with no bridgings used, <bar> to get here with one bridging used, <baz> to get here with two bridgings used [etc], so try <foo+1>, <bar+1>, <baz+1> [etc] on any neighbours".

And when a search tendril includes the possibility to bridge and the upper magnitude measurement (e.g. <baz>) has already used up the possible quota of bridgings, then the <baz+1> is quietly dropped and not propagated across the ignored in the bridged gap.

It does get complicated when a route from one direction featuring a certain number of bridgings meets and travels anti-parallel to a route from another with a different number (with one having the advantage on travel weight, the othr on bridge numbers), and maybe there could be a cut-off other than node-linking strictly per bridges behind them, but the aim is that a path discovery can reach almost to the target area with possibility of both low-cost paths having used up all bridgings (and then ends up rejected if it needs a bridge to take the final step) and at least one higher-cost path having spare bridgings that might end up being the only way to cross.



But I can see alternatives, such as noting each and every bridgable-from nodes in the tree, and when a either a successful path is found or everything ends up dead-ending (with, if available, each of these last-ditch bridgings from that spot also noted) the bridgable-from nodes are reactivated in bridging mode in priority of closeness to destination to search out succesful paths, terminating when those feelers encounter weighted path costs on potential neighbours less than the new weighted path cost it would have imposed to get there via the >= number of bridges on this new mode.  If there's an easy route without any bridging, it should quickly discard all bridgings.  If a short-cut with a single bridge is discovered, it should let that take over as the ideal and then fall back on a search for any two-bridge method (if more than one can be made) that further improves (with note made of potential three-bridge jump offs, if applicable).  And so on while additional bridges are possible.  Instead of a whole heap of "original node map array" + multiple*"N bridges used map node lists" you 'only' have the original node map and one simple list of nodes that you would want to try bridging off (in the following "bridge++" round... if applicable).

Although admittedly what you save on storage, though, you almost certainly lose on time if a quick three-bridge leapfrog ends up being the only solution to a problem, and effectively the entire map had been searched for a zero-bridge one, then a one-bridge one then a two-bridge one... Which goes a bit against the search for optimisation.  (But then again, you could think up scenarios where all the alternatives are less optimal than all others, too. :))


(BTW, I am of course using "bridging" as a shortcut term for any 'consumable' movement, including ladders and trap-fouling with herded animals.  But that does not including 'mining-movement', which would probably be represented by a high-weighting of search paths through the rock, soil or dismantlable barriers, unless the diggers have a finite digging strength/capability of some kind.  e.g. sapper-goblins that exhaust themselves and die (or lie their exhausted), or using stone digging tools that wear out.)



[1] I'm trying to backtrack in my mind how A* deals with the specific example of path A having been pursued heavily due to it aiming advantageously 'closer' to the destination, despite heavy weightings against, and path B being an out-and-back-by-another-route path that is low cost but initially a low-prority in the nominally width-wise search tree, but ends up connecting to A (or, more likely, a not yet fully explored branch of A) with a low weight.

[2] And propogating the lower cost (with appropriate increments) back down the found path.

[3] If a square is so far only reached via a single route with one or more bridging options being exercised then it could be reduced to a magnitude-indicating flag, but as soon as multiple routes with competing "low cost but more bridges v.s. high cost but fewer bridges" routes tag that node, you need to consider a form of duplication.
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #624 on: April 07, 2010, 11:00:00 am »

Effectively this makes every air square within X from a land square potentially passable and so potentially on the network to path. There is no real complexity here at all as we are already checking cost to square as part of the A* search, we don't care if a square is sometimes passable and sometimes not all we care about is the current cost.

Ah, but if you only save two numbers: shortest distance to here, and least bridge material used, then you have to figure out how to get to that square with the least materials if you need all of the material to get across the gap.  A* only stores the shortest path distance to a given location.

So once you have shortest path and least materials you need to somehow workout the actual path that swaps in the middle from following "least materials" to "shortest distance."  If you only follow least materials, then my maze (above) can be transversed using no materials at all (at the expense of distance).  On the other hand, every tile can be pathed to using only the available materials, which could result in the unit attempting to make the shortest possible path (across 3 pits) with not enough materials (eg. the large pit can be pathed across with all my available materials, shortest route to there is across pit #1 -> error: can't cross pit, materials used).
Logged

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #625 on: April 08, 2010, 02:19:21 am »

Ah, but if you only save two numbers: shortest distance to here, and least bridge material used, then you have to figure out how to get to that square with the least materials if you need all of the material to get across the gap.  A* only stores the shortest path distance to a given location.

I said you store shortest distance for each size of bridge which is trivial with A* and means you have no problem with figuring out how to get there, you just follow the path.
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd

Huggz

  • Bay Watcher
  • Sherlock Wayne
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #626 on: April 18, 2010, 07:29:59 pm »

A* is wrong in this situation due to memory usage. I would use the Dijkstra Algorithm.
Logged
Proper English will make people take you more serious.
In order to improve the universe's frame rate, we must all throw rocks into volcanoes and then do absolutely nothing, worldwide, for a week, to take pressure off pathfinding.

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #627 on: April 19, 2010, 03:25:44 am »

A* is wrong in this situation due to memory usage. I would use the Dijkstra Algorithm.

You have the relevant information you need for A* so why would you want to increase your search space?
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd

Huggz

  • Bay Watcher
  • Sherlock Wayne
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #628 on: June 14, 2010, 02:08:40 pm »

A* is wrong in this situation due to memory usage. I would use the Dijkstra Algorithm.

^ Bullshitting. I have no idea what I am talking about, I just wanted to get in on the fun. I <3 Wikipedia! ^
Logged
Proper English will make people take you more serious.
In order to improve the universe's frame rate, we must all throw rocks into volcanoes and then do absolutely nothing, worldwide, for a week, to take pressure off pathfinding.

Thief^

  • Bay Watcher
  • Official crazy person
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #629 on: June 14, 2010, 03:23:50 pm »

Congrats, you've successfully been a waste of time :P
Logged
Dwarven blood types are not A, B, AB, O but Ale, Wine, Beer, Rum, Whisky and so forth.
It's not an embark so much as seven dwarves having a simultaneous strange mood and going off to build an artifact fortress that menaces with spikes of awesome and hanging rings of death.
Pages: 1 ... 40 41 [42] 43