[Jinto]

A* Pathfinding Module

If you would like to know what the A* algorithm is and does.
http://en.wikipedia.org/wiki/A%2A

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:
[list][*]Waypoint saving/loading.[*]Map based waypoint saving/loading.[/list]
Addons for future updates:
[list][*]Waypoint Editor.[/list]
Module function list:
[list][*]astar.CreateSolver[/list]
Object function list.
[list][*]Solver:AddNode <position> <extra cost> <data>[*]Solver:AddLink <first node> <second node>[*]Solver:GetNodeForPosition <position>[*]Solver:ClosestNodeForPosition <position>[*]Solver:Load <file>[*]Solver:Save <file>[*]Solver:SaveMap <name>[*]Solver:LoadMap <name>[*]List:Create <sortfunc>[*]List:Put <node>[*]List:Grab[*]List:HasElement[*]List:Empty
[*]Node.__eq[*]Node:CalculateCost <from start> <heuristic>[*]Node:SetExtraCost <cost>[*]Node:CreateLink <node>[*]Node:GetLinks
[/list]
Block functions:
Block functions are a way to tell the pathfinder whether or not you can travel from a -> b.

Default functions:
[list][*]astar.BLOCKFUNC_TRACE_WORLD[*]astar.BLOCKFUNC_TRACE_ALL[/list]
Example block function:

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

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

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

[Feihc]

Ooooh, fancy. Could prove to be useful

[mblunk]

And here comes the Lua AI.

[Exitus]

How interesting - time for some SNPC

[Galliko]

Wicked.
Will be used.

[terrorclaw]

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.

[Mortal-Wound]

Oh fucking yes! YES!

[Gmod4ever]

Now we need an easy targeting system.

:q:

[Sliverman]

Now lua make AI for NPC? Cool!

[Galliko]

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

[Megiddo]

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. :)

[terrorclaw]

...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.

[andyvincent]

Nice work Jinto!

[Galliko]

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.

[GcDesign]

Very nice work! A* isn't too easy to implement at all...

[Xeon06]

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

[Catdaemon]

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

[Mortal-Wound]

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

[FreeWilly]

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?

[Gmod4ever]

FreeWilly posted:

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.

[Galliko]

Nodes or points.
Really just a vector.

[pyroguy]

You are awesome. I am so going to use this, eventually. I like the idea of a roaming bouncy ball... I also have ideas in mind for assisting simple Strider, Gunship, and Apache AI (as well as other ground enemies).

[FreeWilly]

Oh sorry because I was looking at a strider in the hammer and it had air nodes for the path.

[terrorclaw]

Okay, cool, so I can make mah own paths now it seems >.> or if someone can make a simple to install mod so I can then yay

[Kogitsune]

It's a shame that I don't have an exact use for this yet, because this is pretty cool looking.

[popbob]

This could be used to make new NPC's that walk around, or a turret that hovers around, etc. It's pretty damn amazing.

[terrorclaw]

I hope you can at least make a basic waypoint editor that has maybe visual stuff too it, I accualy love to do pathing and stuff for maps..*shrugs*

[bonecracker]

http://forums.facepunchstudios.com/s...d.php?t=257272
>.>
<.<



time for a combine guard Snpc?

[LoginError]

This would help me greatly in a gamemode i'm making, however...

The download link is dead... :(

Does anyone happen to have a copy?

[Jinto]

LoginError posted:

This would help me greatly in a gamemode i'm making, however...

The download link is dead... :(

Does anyone happen to have a copy?

http://cdbarrett.com/download.php?id...od=view&page=1

[absolute0]

Sexy, Shame nobody is using it.

[LPine]

Ouch! My brain!

[DaddyWarbox]

Nice but... whatever happened to that "industry leading AI" thing all Source games supposedly already have? Can't NPCs already find their way around maps that have their nodes made out?

[Skurmedel]

NPCs made in the Source Engine yes, but not so easily Lua coded ones.

[DaddyWarbox]

What kind of lua created NPCs can there be that can't simply inherit from an existing Source NPC? You shouldn't be having to reinvent the wheel here.

[Jinto]

DaddyWarbox posted:

What kind of lua created NPCs can there be that can't simply inherit from an existing Source NPC? You shouldn't be having to reinvent the wheel here.

There are uses for it outside of NPCs. I didn't create it because I felt I had to, I did because I wanted to.

[IpHa_]

This could be useful if it got incorporated into wiremod.

[tad2020]

Jinto posted:

There are uses for it outside of NPCs. I didn't create it because I felt I had to, I did because I wanted to.

I could see this being used to make some cool laser weapon effect, like from some animes where the beams will bend around obstacles instead of going thought them.

[hoobo]

Cool

[Skurmedel]

DaddyWarbox posted:

What kind of lua created NPCs can there be that can't simply inherit from an existing Source NPC? You shouldn't be having to reinvent the wheel here.

Yes in the case of NPCs you will. Let's say you wanna script an murderous box, in that case, creating a npc_rebel (for example) and setting his model to a box and a bunch of other stuff isn't really the optimal way of doing it. That NPC is made to behave like a rebel, which probably will do, unless you set a shitload of modifiers, and that will probably still present problems.

If you had the real sourcecode you could easily derive the base NPC, add stuff to it and more or less there wouldn't be a limit to what you could do. But we just have Lua and the NPCs that are already there doesn't work in every scenario.