A-Star Pathfinding Module

From GMod Wiki

Third-party Library - A* Path Finding Module
Name	astar
Description:
An efficient and fast A* path finding module that accepts any node system.
Download	http://codepad.org/2GaBIAlE
Source	Not available.
Author	Deco Da Man

Functions

Info

This A* pathfinding module is extremely efficient and can be used with any node system. It's only requirements are that the nodes can be used as unique keys in a table (t[node_a] ~= t[node_b]) and the needed arguments. This means you can use numbers, tables, strings, and even booleans (if you only had two nodes.. which is useless) to represent nodes.. and in combination too!

The 'neighbour_iterator' argument requires a function that returns an iterator function such as the pairs function. An example of such a neighbour_iterator function is:

 
function MyNeighbourIterator(node)
	return pairs(node.neighbours)
end
 

Iterator functions are not limited to pairs and ipairs, you can learn how to make your own iterator functions by the 'hints' in the manual and the various tutorials around the web. Although, pairs and ipairs should do the trick for most situations.

The argument 'walkable_checks' accepts a single function or a table of functions. Each function is given a range of arguments (current_node, neighbour_node, starting_node, target_node, heuristic, ... (the varargs given to the CalculatePath function)) and must return a boolean (true = walkable, false = not walkable). Here is an example of a walkable_checks function:

 
function MyWalkableCheck(current_node, neighbour_node, starting_node, target_node, heuristic, ...)
	return neighbour_node.is_walkablej and TraceBetweenNodes(current_node, neighbour_node, {filters = {...}, this = that}) -- made up function :D
end
 

The argument 'heuristic' is the most important function in the whole thing. It is given two nodes (and the varargs given to the CalculatePath function) and returns a number representing the distance between the two nodes. An example of a heuristic function:

 
function MyHeuristic(node_a, node_b)
	return node_a.pos:Distance(node_b.pos)
end
 

Although simple, it's very important. You can do things such as one way paths with this.

The argument 'conditionals' accepts a single function or a table of functions. Each function is given a range of arguments (the same as 'walkable_checks'), but instead of returning a boolean, it returns a scale factor. If a conditional function returned a scale of 2, it is said that passing from the current_node to neighbour_node is 2 times harder than it should be. 0.5 means half as hard as it should. 1 means normal and so on. 0 should generally not be returned. If you wish to make it so a node is non-walkable, use the walkable_checks argument. An example of a conditionals function:

 
function MyConditional(current_node, neighbour_node, starting_node, target_node, hueristic, ...)
	return neighbour_node.material == lava and 10 or 1 -- makes it consider alternatives and only cross the lava if there is no other path.
end
 

The variable arguments at the end is used throughout the other arguments. You can use it to indicate anything you wish about the situation (weather conditions, locations of enemies, entities to not consider in visibility traces (if you have them), etc).