A* Pathfinding Module

A Pathfinding Module*

If you would like to know what the A* algorithm is and does.

This is a module for developers, it allows them to use the A* pathfinding algorithm easily. Using a waypoint like system.
This will always find the shortest path along those waypoints.

Download: astar.lua

Features:
[ul]
[li]Waypoint saving/loading.
[/li][li]Map based waypoint saving/loading.
[/li][/ul]

Addons for future updates:
[ul]
[li]Waypoint Editor.
[/li][/ul]

Module function list:
[ul]
[li]astar.CreateSolver
[/li][/ul]

Object function list.
[ul]
[li]Solver:AddNode <position> <extra cost> <data>
[/li][li]Solver:AddLink <first node> <second node>
[/li][li]Solver:GetNodeForPosition <position>
[/li][li]Solver:ClosestNodeForPosition <position>
[/li][li]Solver:Load <file>
[/li][li]Solver:Save <file>
[/li][li]Solver:SaveMap <name>
[/li][li]Solver:LoadMap <name>
[/li][li]List:Create <sortfunc>
[/li][li]List:Put <node>
[/li][li]List:Grab
[/li][li]List:HasElement
[/li][li]List:Empty
[/li]
[li]Node.__eq
[/li][li]Node:CalculateCost <from start> <heuristic>
[/li][li]Node:SetExtraCost <cost>
[/li][li]Node:CreateLink <node>
[/li][li]Node:GetLinks
[/li]
[/ul]

Block functions:
Block functions are a way to tell the pathfinder whether or not you can travel from a -> b.

Default functions:
[ul]
[li]astar.BLOCKFUNC_TRACE_WORLD
[/li][li]astar.BLOCKFUNC_TRACE_ALL
[/li][/ul]

Example block function:
[lua]BLOCKFUNC_TRACE_WORLD = function( a, b )

			local trace = {
				start = a.position,
				endpos = b.position,
				mask = MASK_NPCWORLDSTATIC,
			
			};
			local tr = util.TraceLine( trace );
			
			return tr.Hit;
			
		end[/lua]

AddLink will return false if the two nodes in question are already linked in some fashion. Everything was moved into the Solver class. That means you will now do

[lua]mysolver:FindPath( [node/pos], [node/pos], [optional block function] );[/lua]

Ooooh, fancy. Could prove to be useful

And here comes the Lua AI.

How interesting - time for some SNPC

Wicked.
Will be used.

I wonder, is it possible using something similar to the dodgeball or something, if you can make a bouncy ball just randomly choose a number/waypoint, then it will head to it going from point to point to get here, then once it reaches it it will choose another random one and just randomly roam the map…hmmm.

Oh fucking yes! YES!

Now we need an easy targeting system.

:q:

Now lua make AI for NPC? Cool!

No, but it can help you find the shortest path.

A* is a nifty path-finding algorithm. It won’t help you create AI, only to help the AI find their way along pre-determined paths. If you’d like to know more about A*, check here.

By the way Jinto, I’m not sure many of the lua developers here know what A* is or what it means. I wouldn’t know myself if I didn’t have such a fascination with all things AI. :slight_smile:

…So…if I understand this right this lets you, or will let you make new or better ai paths in the maps? shrugs or make paths within the map so they can get around the contraptions you make, or run along them? shrugs I’m mixed up.

Nice work Jinto!

I’ll just explain this…
Imagine a bunch of points scattered around the map.
Now, between those points are paths, or lines (If there’s nothing between those two points ofcourse).
You’re going to set up those points yourself.

Now imagine a Z-formed corridor. This corridor is filled with points.
There’s an NPC at the start of the corridor that have to reach the other end by going from point to point.
Ofcourse it’ll have to choose the shortest path through those points,
'cause we can’t have it make a random zig-zag through the corridor.
This program takes those points and calculates the shortest possible path.
That’s useful if you want an NPC to, for example, find it’s way through a maze or another set of obstacles.

Very nice work! A* isn’t too easy to implement at all…

Wow, awesome, it truly is. I’m gonna test that right now!

That algorithm is used in Unreal Tournament games for the bots I believe. Should be quite useful for RTS games too.

I can’t fucking beleve one of my ideas was actually used!

Awesome stuff, You said “nodes” alot, and I understand that striders move with nodes you can create in the hammer, so does this script allow striders to move on the npc_go command?

No. Not even close.

A node is a place.

It won’t make striders work. Those use path_corner entities.

This uses Lua nodes. :v: