Pathing (Fear pathing, possible tool) discussion.

[Derision]

I decided to revisit a generic pathing solution after I saw the devs over at EQClassic had something working.

Previously I had looked at solutions that didn't require placing manual waypoints, but gave up on that a few months ago.

I have been working on a solution that requires manually placing 'Pathing Nodes', then an automated routine
pre-calculates the connectivity between these nodes, based on LOS and 'Passable Terrain'. The ideal place for
putting nodes is at 'crossroads' between passages, corners, etc.

I instrumented my modified version of OpenEQ to place the nodes and calculate the connections.

This overhead shot shows the path between two abritrary points in SolB. Basically the algorithm looks
for the nearest pathing node which has LOS to the start point, the nearest pathing node which has LOS
to the end point, and then finds a route between the two pathing nodes
via the manually placed pathing nodes (if one exists).



The little red dots connected by red lines are the pathing nodes and interconnections. The Green line
is the path from the start point to the the nearest pathing node. The thick yellow line is the path between
nodes to the final pathing node, and the blue line is the route from the final path node to the final destination.

To be clear, I manually placed the pathing nodes (red dots), but the route was calculated automatically.

This is early days, and I have only had the path finding working in the OpenEQ based tool. Putting it into the game
won't be a problem. Whether it is efficient enough to handle pathing for a complete zone on a populated server
remains to be seen.

[trevius]

Wow, Derison! That looks and sounds really cool! The current way of laying out grids manually isn't way too bad, but anything to help make that easier and more automated would be awesome!

[Derision]

I forgot to say that my focus on developing this is primarily aggro-pathing (to stop mobs running through walls when they are aggroed), but it could potentially be used for less random fear-pathing, and also for roaming NPCs by just specifying a start and end patrol point, rather than all the waypoints along the path.

[YeahlightEQC]

Originally Posted by Derision

I decided to revisit a generic pathing solution after I saw the devs over at EQClassic had something working.

I cannot imagine anything outperforming preprocessed A* pathing: www.eqcprices.com/SebPull.avi (requires XViD codec). It is definitely the way to go and is not that costly if you design it properly (an extra 5MB per zone to store all the pathing data).

[ChaosSlayer]

ok you MUST tell me how did you managed to pull entire zone like that? =)

[Yeahlight]

Easy enough =p

Client Commands

else if (strcasecmp(sep.arg[0], "#pullzone") == 0 && admin >= 255)
{
	for(int i = 0; i < 500; i++)
	{
		Mob* sictar = entity_list.GetMob(i);
		if (sictar && sictar->IsNPC())
		{
			sictar->CastToNPC()->AddToHateList(this, 0, 100000);
		}
	}
}

[Derision]

Originally Posted by YeahlightEQC

I cannot imagine anything outperforming preprocessed A* pathing: www.eqcprices.com/SebPull.avi (requires XViD codec). It is definitely the way to go and is not that costly if you design it properly (an extra 5MB per zone to store all the pathing data).

Your work looks fantastic. If you should ever decide to Open Source your pathing code for EQC, it would certainly be welcome here

[trevius]

Wow, that is really amazing pathing lol! I can only imagine what else you guys might have working!

[So_1337]

That was very impressive.

[AndMetal]

I just added a similar command to #pullzone into Revision 125, #aggrozone, that pulls all NPCs in the zone:



Enjoy