Pathfinding With A*

[Marleys Ghost]

 

For a fuller description please see my blog entry "On The Right Path, A* Pathfinding In Leadwerks."

 

LINK TO DEMO

 

This version of pathfinding is very limited, mainly due to the way I created the node info. But for a first attempt I was quite happy with the end result.

 

The picking can be a little temperamental and sometimes the quickest path is not always found and some "sightseeing" seems to find its way into the route. But on the whole I think it is definitely a platform on which to build.

 

===========================

Controls

===========================

 

Mouse - Camera Look

WASD - Move

Right Mouse Button - Enable Picking

Left Mouse Button (Whilst Holding RMB) Select new position of target object.

Holding down the left mouse button (Whilst Holding RMB)will allow dragging of the target object.

T - toggles if diagonal path movements are allowed or not. (on/off)

Y - switches the spacing of the path "blocks". (lo/hi)

 

Four paths are calculated from each corner of the level to the current position of the target object.

[AggrorJorn]

downloading..

This will be interesting to look at. Thanks for sharing!

[Pixel Perfect]

Looking good MG! Nice to see other people tackling this too. Path finding is an essential foundation for most games that intend to have any kind of NPCs or dynamic moving animated objects that are not directly controlled by the player or players. Not surprising Josh is now talking about including some form of it in version 3, it's just so fundamental I was surprised it wasn't an inherent part of Leadwerks 2. Look forward to seeing how this develops.

[Marleys Ghost]

Josh is now talking about including some form of it in version 3, it's just so fundamental I was surprised it wasn't an inherent part of Leadwerks 2.

 

I think Chris said it best:

 

"Trouble is it's not sexy like all the other graphical fluff... "

 

Its seems there maybe "features" in Version 3.0 that should have been in 2.x, I am not sure I can justify the extra expense when I already have access to those "features", Just not in LE. Yes Path finding is an essential foundation for most games that intend to have any kind of NPCs so I share your surprise that it has never become an inherent part of Leadwerks 2.x

[Marleys Ghost]

Ok, a quick update for anyone interested, this is a revised version which has 3 levels of diagonal calculation now.

 

T - Now toggles if diagonal path movements are allowed or not and to what extent. (lo/med/hi)

 

lo = No diagonals to be calulated in the path.

med = All diagonals to be included.

Hi = Diagonals but only if they do not "cut" a corner.

 

All other controls remain as per lead post.

 

 

 

 

 

I should also have mentioned that the "Path Calculation Time" is the time taken for all four paths to be calculated plus existing path node markers to be deleted and new ones to be created and placed. It is not the time it takes for a single path calculation.

[Marleys Ghost]

Hide And Seek Demo

 

 

 

 

 

 

===========================

Controls

===========================

 

Mouse - Camera Look

WASD - Move

Right Mouse Button - Enable Picking

Left Mouse Button (Whilst Holding RMB) Select new position of target object.

 

B - toggles BotCam

 

When the App opens, the central blue box is the target, way up in the right hand corner is the NPC. Hold down the RMB to allow selection of a new position for the target with the LMB.

 

Hitting B will put the screen into BotCam mode, that is, set a new target position and set the bot walking then hit B to follow it in 3rd Person, hitting B again will return the camera to free flight mode.

 

Limitations:

 

NPC animations are not calibrated as it was not important.

 

No path will be calculated if you pick a point inside a green block, obvious, not so obvious is that grid squares directly adjacent to a green box were reserved for a future path cost assessment between 0-1, as this is not implemented (or even written yet) these grid spaces will act as though they are unwalkable. Still plenty of others though to get the idea.

 

This is all quick and dirty.

 

More information can be found here : The Way Forward ... Making Blitzmax Trax

[macklebee]

pretty slick, MG...

[GIMPY73]

Thats Mint MG.

 

Thanks

Gimpy73

[gamecreator]

Thank you much for sharing this! Since the Leadwerks 3 Roadmap doesn't seem to include pathfinding, this could become very valuable once you have reliable shortest-path picking down.

Edit: I stand corrected. Leadwerks 3 is planned to include pathfinding!

[Davaris]

Its looking pretty darned good MG! Something that works on a grid like this, would be great for turn based strategy games.

[Marleys Ghost]

Hide And Seek Demo 2

 

 

 

 

Demo Application.

 

 

 

===========================

Controls

===========================

 

Mouse - Camera Look

WASD - Move

Right Mouse Button - Enable Picking

Left Mouse Button (Whilst Holding RMB) Select new position of target object.

 

R - Reset NPC's to their starting positions.

 

When the App opens, the central blue box is the target, Hold down the RMB to allow selection of a new position for the target with the LMB.

 

Hitting R will reset the NPC's back to their starting positions and recalculate a new route to the blue box from there.

 

Limitations:

 

NPC animations are not calibrated as it was not important.

 

No path will be calculated if you pick a point inside a green block, obvious, not so obvious is that grid squares directly adjacent to a green box were reserved for a future path cost assessment between 0-1, as this is not implemented (or even written yet) these grid spaces will act as though they are unwalkable. Still plenty of others though to get the idea.

 

There is no mechanism in place for NPC's to avoid collisons amongst themselves yet, this was purely a test of the new NPC Type and methods. They WILL slowly "coalesce" over time. Hence the R button function.

 

This is all quick and dirty.

 

More information can be found here : A* Pathfinding Using Blitzmax And Leadwerks Engine

[gamecreator]

This is simply awesome! I've never used Lua so that's a bit intimidating (I code in C++) but I'm sure this is super helpful for a lot of people. Thanks again!

[gordonramp]

Impressive.