Jump to content

Pathfinding With A*


Marleys Ghost
 Share

Recommended Posts

post-12-067910700 1282336081_thumb.jpg

 

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.

AMD Bulldozer FX-4 Quad Core 4100 Black Edition

2 x 4GB DDR3 1333Mhz Memory

Gigabyte GeForce GTX 550 Ti OC 1024MB GDDR5

Windows 7 Home 64 bit

 

BlitzMax 1.50 • Lua 5.1 MaxGUI 1.41 • UU3D Pro • MessiahStudio Pro • Silo Pro

3D Coat • ShaderMap Pro • Hexagon 2 • Photoshop, Gimp & Paint.NET

 

LE 2.5/3.4 • Skyline UE4 • CE3 SDK • Unity 5 • Esenthel Engine 2.0

 

Marleys Ghost's YouTube Channel Marleys Ghost's Blog

 

"I used to be alive like you .... then I took an arrow to the head"

Link to comment
Share on other sites

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.

Intel Core i5 2.66 GHz, Asus P7P55D, 8Gb DDR3 RAM, GTX460 1Gb DDR5, Windows 7 (x64), LE Editor, GMax, 3DWS, UU3D Pro, Texture Maker Pro, Shader Map Pro. Development language: C/C++

Link to comment
Share on other sites

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

AMD Bulldozer FX-4 Quad Core 4100 Black Edition

2 x 4GB DDR3 1333Mhz Memory

Gigabyte GeForce GTX 550 Ti OC 1024MB GDDR5

Windows 7 Home 64 bit

 

BlitzMax 1.50 • Lua 5.1 MaxGUI 1.41 • UU3D Pro • MessiahStudio Pro • Silo Pro

3D Coat • ShaderMap Pro • Hexagon 2 • Photoshop, Gimp & Paint.NET

 

LE 2.5/3.4 • Skyline UE4 • CE3 SDK • Unity 5 • Esenthel Engine 2.0

 

Marleys Ghost's YouTube Channel Marleys Ghost's Blog

 

"I used to be alive like you .... then I took an arrow to the head"

Link to comment
Share on other sites

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.

AMD Bulldozer FX-4 Quad Core 4100 Black Edition

2 x 4GB DDR3 1333Mhz Memory

Gigabyte GeForce GTX 550 Ti OC 1024MB GDDR5

Windows 7 Home 64 bit

 

BlitzMax 1.50 • Lua 5.1 MaxGUI 1.41 • UU3D Pro • MessiahStudio Pro • Silo Pro

3D Coat • ShaderMap Pro • Hexagon 2 • Photoshop, Gimp & Paint.NET

 

LE 2.5/3.4 • Skyline UE4 • CE3 SDK • Unity 5 • Esenthel Engine 2.0

 

Marleys Ghost's YouTube Channel Marleys Ghost's Blog

 

"I used to be alive like you .... then I took an arrow to the head"

Link to comment
Share on other sites

Hide And Seek Demo

 

post-12-066210600 1282602581_thumb.jpg

 

 

 

 

 

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

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

AMD Bulldozer FX-4 Quad Core 4100 Black Edition

2 x 4GB DDR3 1333Mhz Memory

Gigabyte GeForce GTX 550 Ti OC 1024MB GDDR5

Windows 7 Home 64 bit

 

BlitzMax 1.50 • Lua 5.1 MaxGUI 1.41 • UU3D Pro • MessiahStudio Pro • Silo Pro

3D Coat • ShaderMap Pro • Hexagon 2 • Photoshop, Gimp & Paint.NET

 

LE 2.5/3.4 • Skyline UE4 • CE3 SDK • Unity 5 • Esenthel Engine 2.0

 

Marleys Ghost's YouTube Channel Marleys Ghost's Blog

 

"I used to be alive like you .... then I took an arrow to the head"

Link to comment
Share on other sites

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

AMD Bulldozer FX-4 Quad Core 4100 Black Edition

2 x 4GB DDR3 1333Mhz Memory

Gigabyte GeForce GTX 550 Ti OC 1024MB GDDR5

Windows 7 Home 64 bit

 

BlitzMax 1.50 • Lua 5.1 MaxGUI 1.41 • UU3D Pro • MessiahStudio Pro • Silo Pro

3D Coat • ShaderMap Pro • Hexagon 2 • Photoshop, Gimp & Paint.NET

 

LE 2.5/3.4 • Skyline UE4 • CE3 SDK • Unity 5 • Esenthel Engine 2.0

 

Marleys Ghost's YouTube Channel Marleys Ghost's Blog

 

"I used to be alive like you .... then I took an arrow to the head"

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...