Fear Pathing Once Again

[fathernitwit]

ok, well after thinking about this and people talking at me about it.. here is a solution I propose to implement fear pathing.

99% of the work in this will be in an external program, so I dont give a shit about runtime.. it can take 5 hours a zone for all I care, it only needs to run once. The emu code to implement it will be trivial once we have the pre-calculated path files.

anyway, here goes, in nice cant-sleep-writting-down-ideas notation:
(sorry for the code block, its pre-formatted)

** Load up our data in raw format:

load the map for this zone

load all waypoints for each grid

connect each waypoint in a grid
 - connect begining to end? maybe only if its a short link and it has LOS

try to lower waypoints way in the sky:
 - do not wanna drop people below docks though, so set min height first
 - for each waypoint/spawn point
   - if the best Z below the point (+6 on Z) is more than DROP_HEIGHT
   - then lower the waypoint to bestZ + 10ish

run a waypoint reduction algorithm in 3space:
 - For each waypoint W where 0 <= W < N-2
   - determine unit vector from W to W+1
   - determine unit vector from W+1 to W+2
   - dot product the two vectors
   - if the dot product is very close to 1.0, eliminate W+1, and connect W to W+2
   - Run code from node W again, dont go to W+2 next

load all spawn points

** connect up our graph:

run algorithm to connect all grids to eachother
 - form one large connected graph
 - maybe choose several connection points for each grid
   - only if they are very different (begin, middle, end?? 3 closest disjoint?)
 - check LOS for each connection
 - avoid large Z variance if possible

run algorithm to connect all spawn points to the big grid
 - first find the closest node we have LOS to
 - optionally try to find a second node too, just to give us more options
   - I am not sure if this will buy us anything... since MST will very likely kill this link
   - find the second closest node which has a vector thats not close to the closest
   - for each node in big grid N
     - Check LOS between mob and N
     - find distance from mob to N, if not possibly 2nd closest: continue
	 - determine
   - check LOS for each connection
   - connect to 1 or 2 of the closest points (prolly 2 if possible)
   - avoid large Z variance if possible

run an algorithm to remove redundancy:
 - Two points close to eachother (connected or not): merge links into 1, delete other
  - for each node, check dist to all other nodes...
 - Two of the same link after merge: delete one
  - for each node, for each link in that node, see if its the same as any other link
  - do we need this? MST will eliminate these, but will run slower

maybe scan for nodes with 256 or more edges leaving them, and do something??

** now we have a huge connected graph that should have valid paths.

run a minimal spanning tree algorithm
 - if possible, make it consider not having more than 255 edges from a node

** now we have a minimal connected graph such that any mob can get anywhere
   by only a single path.

Things we might want to do now:
 - Try to create some cycles. Specifically large cycles.
   - these will add more realism to the pathing
   - might be implemented like this:
     - run all pairs shortest path on the MST (is this a byproduct?)
	 - for each node N, for each other node K
	   - if path(N, K) is at least MIN_CYCLE_JOIN_PATH (to prevent making small cycles)
	   - and dist(N,K) is less than MAX_CYCLE_JOIN_DIST (do not want to invent long paths)
	   - and there is LOS from N to K
	     - connect N and K
		 - have to re-run all pairs again... that sucks
   - another twist on the implementation would be to only look at paths
     which were discarded by the MST. Or maybe run this first, then the other.

** now we have our final pathing grid. determine some useful info for each node.

look for dead ends/node preference:
 - at each node, sum up the length of all edges reachable by using that link
   - for each node as N
   -- for each edge leaving N as E
   ---- reset marks on all edges
   ---- mark all edges leaving N
   ---- perform a depth first search of all reachable nodes
   ------ Only traverse unmarked edges. Mark each edge as it is traversed.
   ---- unmark all edges leaving N, except E
   ---- sum the length of all marked edges
   ---- store this reachable length as a weight for this edge of this node.
   -- for each edge leaving N as E
   ---- determine highest edge weight in this node
   -- for each edge leaving N as E
   ---- count number of edges within RANDOM_WALK % of the highest node.
   -- sort the edge list for this node to have all random nodes first
   -- store the random walkable counter for this node
 


** Finally we have all the calculation

things we need to store:
nodes
edge lists
quadtree containing nodes

 - We do not really need to store edges which are not on the random walk
   list since the pathing code will never consider using them.

Node {
 x, y, z
 edge list pointer
 edge list length
 random walkable counter
}

edge list entry {
 ending node pointer
 reachable edge weight? (not used by pathing, might have other purpose)
}

quadtree node {
 minx, maxx, miny, maxy
 union {
  node pointers: q1, q2, q3, q4
  node list offset and length
 }
}




how to do fear pathing...
when a mob is feared, it uses the quadtree to find the node closest to it
that it can see to. The LOS requirement will make this more difficult, but feasible.

Once it has found its first node, the mob will set this as its waypoint and go there.

Once the mob reaches a node, it will look at the node's random counter (RC)
 if RC is 1, take the first edge and use its terminal as next waypoint
 if RC is >1, randomly choose an edge from 0 to RC-1, and walk that edge.