Kamis, 29 November 2012

Working A* pathfinding

The A* pathfinding system is now functional and very efficient, guards quickly generate a route to the player using the nodes placed on the map and then optimize the route deleting any superfluous nodes on the path. I ended up not using the arrays built into the nodes of closest other nodes because I would have to use that array and the open list of nodes on the pathfinding script at the same time constantly cross checking that a node in the node's array was also on the script's array and then finding the chosen node from the node's array in the script's array to remove it from the open list. I decided it would be more efficient to just check all nodes.
(Above) The pathfinder with no optimization finding the first route through the nodes to a set point. (Below) With optimization code (And fewer nodes) the script finds an efficient path to the target. Also switched to spherecasting instead of raycasting because rays were cutting corners too close and guards couldn't get past comfortable and from time to time would try to find paths through arrow slits.
One more addition needs to be made before the script is ready to be implemented by the guard movement script, that is back tracking. I haven't run into any problems that would need it yet, any failures of the pathfinding so far have been node placement related but as levels get larger and more complex it's probable that guards will start taking dead ends and the pathfinder will get stuck at the ends of hallways instead of reaching the target. To solve this the script needs to be able to backtrack one node at a time. So ad the end of the dead end it realizes its mistake and moves back one node and looks for a new closest node disregarding the previous choice, either it finds a new path or it moves back again until a new path is available.
Once all this is implemented guards will need some sort of smoothing to make their paths look more natural, also they may run this script over the course of a few frames to make sure it always runs smoothly and the guards don't need to move immediately anyway, a few frames to notice the sound or sight, then a few frames shouting out or looking around will only look natural.
templates-office.com Pathfinding, Stealth