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.

[mollymillions]

[font=Arial][size=2][font=Arial][size=2]Would it be worthwhile to include all the spawn points when initially connecting all the waypoints into a big grid? I only suggest this as will take care of all of the spawn points that have LOS to a waypoint, any remaining spawn points (those that don

[RangerDown]

EQLive seems to use a big grid of geometrically-aware waypoints. And in the fashion of a fire drill floor plan diagram, it seems to have logic that "if you're in THIS area, you'll use THIS route for fearing; if you're in THAT area, you'll use THAT route for fearing..." If you fight multiple mobs in the same general area of the zone, you'll observe them using the same routes on their fleeing path.

[mollymillions]

Fathernitwit, I am keen to get started on this and am wondering how its going happen, i.e. a new project on Sourceforge, a new console app and directory in the existing EQEmu project (post code in this thread)?



*edit* (I had no idea there were so many grids in each zone, have a look at the freportw grids http://members.dodo.net.au/~mollymil...ortw_grids.jpg)

[fathernitwit]

ah well I guess I will give a status update.

Path file generation is going very well. It is in a standalone console application, just like map building. If the zone has good pathing, or lots of mobs close together, then it is getting great results. On the other hand, sparsely populated zones are gunna need some manual tweaking, through the use of in game commands to add new hint points. It is still generating minorly invalid paths, and the only way we are gunna get away from that is to give it incentive to generate the right graph instead by providing more hint points.

Some of the biggest obstacles I have come across:
- Invalid data in the database... how to identify it. (not great yet)
- Newbie fields and high-pathing zones needed a HUGE reduction algorithm run on them.
- Eliminating small, disconnected subgraphs from the whole mess

The only real challenge I have remaining is supporting multiple disjoint fear grids in a single zone, like will be the case in ToFS. Need to identify them, and process them seperately.

Here are some example zones and their paths. Grey is the source data, and red/orange is the final fear paths, colored by z height.

Good dungeons:
http://www.projecteq.net/fathernitwi...one-mstree.png
http://www.projecteq.net/fathernitwi...der-mstree.png
Good Cities:
http://www.projecteq.net/fathernitwi...nos-mstree.png
http://www.projecteq.net/fathernitwi...os2-mstree.png
http://www.projecteq.net/fathernitwi...ark-mstree.png
Needs help examples:
http://www.projecteq.net/fathernitwi...her-mstree.png
http://www.projecteq.net/fathernitwi...per-mstree.png


These grids get put into a path file, which includes a quadtree for fast searches. The format is very similar to that of the map files.

On the emu side of things, I have code written to read in the path files at zone bootup. I can them locate the closest path to me, and run to it. Then once I reach that node, I can select the next node, etc.. so essentially it works. This is just raw testing, I dont actually have mobs running on the path, but that is trivial with the WP code. I have an issue where my code to decide where to go next is getting into a small loop and running between just a few nodes, but im working on a fix for that.

One thing im trying to decide on is what to do when I cannot locate a closest fear node. Like if we are in a place where there was no pathing/mobs anywhere near us, etc... Or in a small room that cannot see any of the nearby points. it seems like the only solution is to use what we do now, since nothing else is really reliable in emu. Theres more possibilities in the processor, but that will rely on LOS, which is not 100% perfect.

Basically, the code will be done soon, its just a matter of hand-tuning all the zones so we can get good path files.

processor is about 3500 lines right now.
emu code is about 1000

[RangerDown]

If you have no node near you, the best thing you can do for fear is just pick a node and, even if it's halfway across the zone, take a direct route to it. Through walls, through trees, it doesn't matter. Part of the danger of using fear is you can't be 100% certain where a mob may choose to run. IMO, the worst thing you can do is either have the mob stand still, stunned. Doing so will only encourage players to pull mobs to that spot and fear them from there.

If you're really up to a challenge, generate fear pathing in Kedge Keep and see what it did. Don't beat yourself up if it fails miserably in that zone -- all Kedge mobs EQLive are unfearable for that very reason. So if it can generate even halfway decent fear paths for that zone, you're already doing better than Verant ever could

[mollymillions]

[size=2]OK, I feel pretty foolish for posting now, I assumed this was sitting on the back burner as it has been for a long time, although it was only last night that I started researching (and coding) and found how much discussion had occurred in the past. I guess I should cruise my couch some more and wait for it to be finished.

There isnt much actual EQEmu development discussed in this development forum? I feel I should be working on something but don