Print

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

[NW_Kohaku]

If portals were connecting two entirely different chunks of terrain, and there was only one portal between the two, there would be no major pathing difficulties.  Essentially, any path from a point inside one dimension to another point inside the same dimension would be unaltered.  A path between dimensions would simply be pathing from where you start to the portal, and then from the portal to the destination.  In determining the distance from where you are to an object before pathing, to see what the closest object that can be obtained is, then simply add the distance to the portal to the distance any given object is from the portal (as the mole digs).

If dimensions are hypercube-style, it actually wouldn't be THAT much more of a problem to path.  Computers do not see dimensions in the same way we do - computers view dimensions as Cartesian Coordinates in the matrix data structure used to create such relative distances.  2-d space to a computer is just an array of arrays.  3d space is an array of arrays of arrays.  4d space would just be an array of arrays of arrays of arrays.  Pathing would then simply have an extra set of potential moves each time it tried to move towards the target, resulting in a change from 26 theoretically possible moves to 80 theoretically possible moves (roughly tripling, but again, only in a worst case, as with a flying unit who could move unimpeded).

The real problem for programming would come when you start having multiple intra-dimensional portals.  ("Now you're pathing with Portals!") If it were possible to make a trip that took 100 steps in a straight line instead take 10 steps to get to a portal that would instantly drop you out 10 steps away from your destination, then the portal would be a faster route. (Or even if the first portal 10 steps away takes you to another plane, where another portal 5 steps away would take you to the portal that is 10 steps from your destination.)  This causes major problems, as there is no real way to know if going out of your way to catch a ride in a portal will make a trip shorter until you actually test pathing that.  Meaning that every time you path, you have to check for every combination of portal routes, which would exponentially raise the number of times you have to make pathing checks by the number of portals in play.

[fanatic]

You guys realize that pathfinding would grind a multi-dimensional fortress to a halt in no time, right?
On a more positive note,   pumping magma through a 4-th dimension rift sounds awesomely dwarfy to   me

It does not. The pathing changes a bit but thats it. The Pathing would just calculate over 2 Grids instead of 1 as soon it encounters a open Gate. Thus it could - with a number of portals - even speed up. Said that you can even ignore the other dimensions if there is only one gate leading to them. 

Also by "dimensions" are - in this thread - Parallel worlds ment as in "Hugh everets theory of multiple worlds" or "Alternative reality's in a Multi-verse" not Objects/places with more then 3 room-dimensions (like a Hypercube).  Just saying to clarify any misunderstandings.

(i know its a little bit more complicated then that. But for **** sake not everyone here has a degree on computer-science/physics or similar stuff. )

You can turn it the way you want i doubt multiplying the number of tiles by the number of parralel worlds is going to help the pathfinder. if we assume portals can be open between any two tiles of any different planes, this likely will increase the number of paths to check drastically.

Also, i find quoting Wikipedia articles on cosmology/mathematics disturbing... Its like quoting mythbusters on engineering. but maybe thats just me.

[Mel_Vixen]

Yeah sure its not like they link to any sources or that many of this artickles are already locked. Wikipedia is not as much trustable as any other .... uh Enceclopedia printed or otherwise.

[Huggz]

I second the idea of different planes, but not more dimensions - not everyone understands 4-dimensional space...

It wouldn't need to be genned until you embarked with a fort - take the local area, warp it and add fire/earth/air/water (whatever, you get my point). For adventure mode, I suggest only being able to enter through predefined portals (such as in dark towers) and the elemental planes for those premade portals would be generated with the world.

[FreakyCheeseMan]

I second the idea of different planes, but not more dimensions - not everyone understands 4-dimensional space...

It wouldn't need to be genned until you embarked with a fort - take the local area, warp it and add fire/earth/air/water (whatever, you get my point). For adventure mode, I suggest only being able to enter through predefined portals (such as in dark towers) and the elemental planes for those premade portals would be generated with the world.

Well, four dimensions is just the easiest way to do it. It won't be *that* much like four dimensions, because it will only matter at one point- the portal. It's pretty much just scrolling between entirely sepearte maps of the same size.

I don't think you'd have a lot of control over where portals opened... maybe. I'm thinking "Passing Wizard Do it", "It Just Happens" or "Artifacts Go Wrong". The last one would be the only one to give you control... maybe portal-happy artifacts would have some hints that they'd open one, so you could move them? Or maybe include a "shrine" building, where artifacts can be placed for display, which will also "power" their magical properties.

[nbonaparte]

You could avoid the pathing problems with portals by having them be pregenerated features scattered around the world. It would be far simpler to calculate the distance from any one point on the map to any other through the portal while the game's loading up the map, and not have DF calculate it on the fly when a dwarf wants to go somewhere.

[FreakyCheeseMan]

You could avoid the pathing problems with portals by having them be pregenerated features scattered around the world. It would be far simpler to calculate the distance from any one point on the map to any other through the portal while the game's loading up the map, and not have DF calculate it on the fly when a dwarf wants to go somewhere.

Not... really. You could just generate that whenever a portal opens or closes, so it doesn't have to be done on the fly, and that way there's no need to have them be set in stone- half the fun would be having a portal to the elemental plane of fire open in your booze locker when you weren't expecting it.

[nbonaparte]

True, that would be more dynamic and in the style of DF.

[FreakyCheeseMan]

I'm going off of something Toady said once- artifacts should be more interesting, and maybe dangerous. A dwarf might make a flaming sword, but one day it might get enough kills and open a portal to the dimension of fire, was what he said. I really like that idea... having more half-controllable events that you can manipulate to an extent, but not really rely on.

[NW_Kohaku]

Well, again, it wouldn't create pathing problems if there was only one portal between any two dimensions, no portals that teleport you from one point on a given dimension to another point on that same dimension, and you simply wouldn't path "stopover" routes between three dimensions with a "triangular" connection path.

If you make all paths inside of a dimension never even consider using portals ("Now you're thinking WITHOUT portals!"), and make trips between dimensions be pathed as "Part 1: I path to the portal as per normal, and Part 2: I path from the portal to the destination in the destination dimension", then you aren't going to need to fundamentally change pathing procedures.

[Nil Eyeglazed]

Even if you don't want to think about it in terms of a 4th dimension, really, that's how it would be implemented; even a single three-dimensional parallel "plane" acts exactly as a 4th dimension, just without significant depth to that 4-d z-like-level.  The hit on pathfinding would be directly proportional to how many portals existed through that fourth dimension, and how deep that fourth dimension was.

Pathing through a single corridor that wound through the fourth dimension would not be any more intensive than pathing through a single corridor that wound through the z-axis.  These are all equivalent pathfinding tasks:

Code: [Select]


top view

###
___
###

top view

###
__#
##_

side view

#>#>#
#<_<#
#####

top view, P1 and P2 are portals through another plane

###   ######   ###
_P1   P1__P2   P2_
###   ######   ###



On the other hand, pathfinding chokes on large open spaces.  A 10x10X10 room full of up down staircases is up to 10 times as intensive to path through as a single z-level 10x10 room, and would consume as many cycles as a single z-level 10x10 room filled with portals; if portals and up/down staircases could occupy the same space, then you could make a 10x10x10 room full of them that would take 1000 times as much cpu to path through as a corridor.

So then, if you like the idea of extra dimensions, but don't like the cpu hit, don't make big rooms full of portals

[NW_Kohaku]

stuff

The problem with that is what I said a few posts ago about portals that reconnect inside the same plane...

A z-axis is not a significant threat to pathfinding (it certainly will potentially geometrically increase the pathfinding cost, though) because we ultimately still have pathing weights that will make sense - diverting around a wall on the z-axis by climbing stairs to go over that wall, and back down, is fundamentally the same as pathing around it on the x- or y- axis by walking to a doorway to bypass the wall.  This is because going up one z-axis level before moving across seveal x- or y-axis spaces moves you just as far as just moving on the x- and y-axis alone, excepting the cost of moving across the z-axis.

Using portals, however, unless you make all portals in all parallel planes have 1-to-1 mapping, so that if Portal A on Dimension 1 is 5 x east, 12 y north, and 3 z above Portal B on Dimension 1, then it means Portal A on Deminsion 2 is 5 x east, 12 y north, and 3 z above Portal B on Dimension 2, then you open massive pathing problems. 

What if, as I said before, you have a path where it is a straight line to move from point A to point B on a single dimension, perfectly clear of obstacles.  Current pathfinding would almost certainly just draw a beeline towards Point B, no questions asked, because it starts from the assumption that a straight line is the fastest route between two points, and doesn't check for alternatives until the straight line is proven impossible.  Then, it starts looking for the smallest diversion it can possibly take to reach the same goal, assuming that the closest thing to a straight line would then be the fastest route. 

This doesn't always happen, of course, truly labarynthine forts may force pathing through virtually every tile it can find access to before it can find a valid path, but the assumption that it should start with the best/most likely/fastest case, and then check progressively less good paths is the fundemental way in which pathfinding can be economized, because if it checks the assumed best path first, and finds it, then it doesn't need to search for any more paths.

This, however, goes completely out the window when you introduce portals that can skip you around.  Suddenly, the fastest route becomes jumping through hyperspace by walking away from the destination to reach a nearby portal 10 tiles away from which it can simply walk a few steps in another dimension to find a portal that will drop it 10 tiles away from its destination in the original dimension.  Because pathing away from your destination suddenly becomes a viable means of shortening the route to your destination, the notion that the shortest route is the closest thing to a straight line you can get is no longer true.  This means that the fundamental assumption that the quickest thing that looks the most like a straight line will be the best path is no longer true, meaning that in order to optimize travel time, pathing will have to check every possible path that uses a portal to get to the destination, and compare that path with the straight line route, because straight lines are no longer assumed to be the shortest distance.

[FreakyCheeseMan]

Hrrm.

So, to be fair I don't know pathfinding, but... a few points.

First, I don't think anyone is proposing portals *not* be one-to-one, as you described it. They'd be rare enough things anyway, you'd probably never get two going to the same plane, so what would be the point of having them link to different parts?

Secondly, you sure about the straight-line thing? I could have sworn it was more complicated than that... like, the game keeps a web of existing routes and paths through those?

[NW_Kohaku]

Is there something like a "favorites" folder for threads?

http://www.bay12forums.com/smf/index.php?topic=56041.0

This thread basically explains how pathfinding works.

Creatures pathfind every time they try to go anywhere because it is assumed that the map is dynamic enough that storing pathing data is not really worth it.  This is why it is so particularly painful to have pets try to get out of closed doors - they pathfind to a place they want to go continuously, then bump their head on the door, try to find a way around, pathing to basically every part of the fortress, then giving up, then forgetting that all, and deciding they want to go somewhere, and bumping their head on the closed door...

[Nil Eyeglazed]

I'm not totally sure that I understand what you're saying.  But I think I do.

I certainly was working under the assumption that there was a 1-to-1 correspondence through additional dimensions.  I don't believe it would matter at all though.

If I'm understanding you correctly, then we don't share the same idea of how pathfinding works in this game.  My understanding is a sort of flooding system, whereas yours sounds like looking for paths until you find one.

Current pathfinding would almost certainly just draw a beeline towards Point B, no questions asked, because it starts from the assumption that a straight line is the fastest route between two points, and doesn't check for alternatives until the straight line is proven impossible.

That's not my understanding.  It will draw a beeline as a baseline, and establish a pathing cost; then it will explore alternative paths until those alternative paths are more costly than the baseline.  If an alternative path proves less costly than the baseline, the alternative will become the new baseline to continue evaluating alternative paths, until all possible paths have been evaluated as more costly.  This is the principle that permits traffic designation.  If the beeline is restricted, two straight squares might cost 50 pathing points, meaning that alternative paths might be explored up to 50 squares before the restricted beeline is used; if the beeline is high traffic, and no others are, then path checking through alternative routes will still occur, but terminate at the first square (leading to a lot fewer paths explored, since those alternate paths will grow out of a small number of initial, abandoned paths).

So let's look at a hypothetical portal situation, which is what I think you're saying would cause serious problems:

Code: [Select]


our dimension; P1 and P2 are portals

P1>___________<P2

alternate dimension

P1_P2


So in this case, the engine checks a pathing cost between the two staircases first as the crow flies, and it sees a cost of 12 squares.  Then it evaluates alternate paths.  If any alternate path reaches a cost of 12, the engine gives up on that path.  So it pursues the path as Azathoth flies, sees a pathing cost of 4 squares, and abandons the original path; if further paths are evaluated, they'll be abandoned after reaching a cost of 4 squares.

EDIT: I made some simplifications to this that I feel I ought to point out.  The pathfinding does not actually test a path to completion before moving on to other paths; since it's going to eventually evaluate every path to a certain distance, it evaluates in parallel.  In the example above, the game would first evaluate the first square of the crow's path, then the first square of the portal path, and wouldn't ever really evaluate the crow's path to its conclusion.  By evaluating in parallel, the game knows that it has found the shortest path when it finds its first path.

EDIT2: Disregard everything I said   I believe you're correct, Kohaku-- if the game uses A* pathing, then a 1-to-1 correlation is necessary for shortest pathing.  Things wouldn't be broken entirely, but you couldn't count on your dwarfs taking advantage of potential shortcuts.