Print

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

[Niseg]

Once an HFS finds a target, I don't believe they continue the BFS every frame, but I do believe they will seek a target until they find one-- and I don't necessarily see anything wrong with that.  It could be and should be improved with a proper set of connectivity maps that take fliers into account, of course, but the aggressiveness isn't the problem.

HFS can be walled off once breached, which causes severe slowdowns.  Furthermore, there are MASSIVE numbers of HFS, and they respawn (albeit slowly).  This causes a LOT of said BFS.

you are talking about the O((k/2)^N)~ complexity of A* and the no-path penalty = worst case. HFS has a big N and the clowns have big k (the got lots of flags).

Regardless though, the key here is to make a pathfinding system that is efficient for ANY movement type-- walking, flying, swimming, magma... heck, add in digging, climbing, maybe even jumping... and while we're at it, might as well add in multitile movement as well.  It must be robust to handle these kinds of things.

That stuff is trivial  I can easily do it  with my room system (have to turn simulator to 3d add obsticles of diffrent types). All I'll do is add in all the collisions of interest to the list and go through them to calsify movement type on an edge.


Anyways I went alittle crazy with my simulator and made a 128X128 version  . you'll see most of the stuff I did in this thread.
http://www.bay12forums.com/smf/index.php?topic=83804.0

My algorithm runs 1000 times faster than A* and needs about 100ms~ preparation type (no cache version). A* runs on a graph that size using 190~ million iterations (13~ seconds) . I manage to keep it small at about 47000 (14~ms) which is about 2000 iterations per subpath.

EDIT: I made A* run much faster using two bit vectors - one for open and one for closed set.
EDIT2:  insert in order is in now.  A* is orders of magnitudes faster than the original  by replacing linear search with the bit vectors and making all the pushes inserts in order which is log N time (best node always in front). With a regular A* Which is a node explosion it reduced runtime by a lot because it's (k/2)^N is much larger.

[sockless]

http://en.wikipedia.org/wiki/Ant_colony_optimization

Might be something interesting for you folks to look into. Essentially a DFS with Heuristics if I'm not mistaking.

[Draco18s]

The problem with an Ant Colony Optimization is that it depends entirely on a single starting location compared to a single ending location (the traveling salesman solution is also not viable for DF, as it's a round trip through multiple locations) when what DF needs is a multi-start, multi-end solution.  The "get from any stockpile to any other stockpile" type solution.  You can't just track pheromones, as it'll just end up a useless mess (observe blood in a fort: in any tile that has blood, assume that it has high pathing frequency, thus large pheromone count, is this collection of tiles useful?).

The problem is one of "multiple actors, same job" versus "single actor, many jobs."  The Ant Colony is the former, DF is the latter.

[ferok]

The whole point of threads and "slicing" is to transfer processor power onto another task while waiting for a memory fetch.  This is something that has existed for decades.  Thing is, DF is not multi-threaded, so all this means is that your processor will spend its time working on all the other programs running on your computer during this time.

That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.

[Niseg]

that ant farm reminds me of path caching which has a big penelty when a path to the destination doesn't exist. you also need a path smoother but that is not to bad in terms of complexity.

my room spliting is a beter choise but i need to figure out an update scheme. you can practicaly regenerate all of them every 1000 frames and be fine. that is not optimal though.

it reduces complexity,  split the path and has a low penalty.  the room system can also help finding the closest item.

it has. room for improvment but. it works. well as is.

posted from a PDA sorry for the bad English ...

[tps12]

That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.

Interesting! I think this whole thread is dedicated to extreme pedantry, so no worries.

[devek]

The whole point of threads and "slicing" is to transfer processor power onto another task while waiting for a memory fetch.  This is something that has existed for decades.  Thing is, DF is not multi-threaded, so all this means is that your processor will spend its time working on all the other programs running on your computer during this time.

That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.

If we are going to be pedantic... Threading was not invented to split work between cpus, as threads were invented long before any computers that had multiple processors. To say that the environment of threading in single processor environments only exist in very few places would only be correct if you never made a phone call or drove an automobile.

Userland threads, or N:1, are so useful for their low overhead that there is an entire programming language called erlang for it. 1:1 threading overhead on lesser platforms like Linux and Windows are so horrible, programmers go out of their way to make as few threads as possible because many programs end up being faster single threaded or compiled with userland threading.

[Niseg]

I'm thinking of improving my room model by removing the bitvector description of from the room object and leaving the edges. I'll use the output of my BFS collider as a lookup table of O(1) to find if a node is in a room . Then adding an update scheme would be much easier but the data structure might take a lot of memory but I can add some kind of scheme to reduce it to 1 byte per node or less .

The update scheme would look at a collection of nodes that changed from either wall->floor or floor->wall. A floor->wall is the easier case because at worst it would block or or more access point and removing edges is the easy. a wall->floor change would require looking at all its neighbors and decide which room it should be added to and then update that room and its neighbors .

Other than that I'm thinking about defining the access point using some kind of line or vector . I think the rooms I created can be easily converted to nav meshes and then path finding between them would be very trivial. due to a polygon shape you can just draw line between then without any collisions .  I can also implement a vector method with an A* to walk around obstetrical . This should usually reduce the complexity to almost nothing because it would shorten the space A* would have to look at to nothing.

Even though my rooms don't look nice and rounded it is not really critical for the scheme to work.  I might have mentioned this before but my scheme only look at around 3-4% of the nodes as opposed to A* who looks at over 40%. A* also take more iterations to find the target - about 20 times more (come from insert in order optimization only it used to be more computationally intensive) .  My scheme also support spreading the pathfinding algorithm to many time slices instead of one huge step. no path penalty is extremely low while A* penalty is extremely high .

More things can be added to this scheme like finding the closest item according to the room it's in . This way dwarves won't use a blind heuristic to pick their stones. This can also be fixed with a line of site penalty heuristic like i did in my calculator it draws a line, validate it and add 2 for every  wall it hits (the minimum distance to go around it).it can be made smarter than that.