Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
  • entries
    50
  • comments
    173
  • views
    93,705

On The Right Path, A* Pathfinding In Leadwerks.


Marleys Ghost

1,706 views

Well, it has been a while since I made a blog entry, let alone done any work in LE. But I do keep an eye on the forum and Leadwerks in between Daily life and working on my project(s).

 

I have also been going through my Blitzmax code archive, where I stored all my Blitmax/LE projects and code snippets (finished and not completed). One idea I had been playing with before, was basic NPC AI. I had some small success with some Bugs using autonomous logic.

 

See Here

 

In my "treasure trove" of unfinished and messy development code I found what was going to be the next step (for me) with AI functionality. The dreaded "pathfinding". I have read that Naughty Alien said he will be doing a two part tutorial on this and I am looking forward to that, having followed his work with Hidden Dawn I expect the tutorial to be top notch. But I wanted to get to grips with the in's and out's myself. So I started with the basics. I spent some time looking for code snippets and A* lib's in any language that had them to see of I could follow along what was being done ... Not a good place to start, in the end I spent some time reading "A* Pathfinding for Beginners", very helpful.I decided it would be best to start with a "2D" approach and maybe use nodes. Most 2D implementations use a grid based on the X and Y co-ordinates of the screen and tiles to represent an "unwalkable" tile. So I thought I would translate this approach to a 128 x 128 flat terrain with some primitive models to define the "unwalkable tiles". As this was a time limited "side-track" in LE from my other projects, it was all going to have to be quick and dirty. I wrote an app to calculate which "tiles" of the 128 x 128 terrain did not have an obstruction and then squirted this data out to a text file to be read into another app as a 2D array. The map data loads in a few milliseconds so this eliminated having to wait for the same data to be generated by the application I wanted to use to try and get the pathfinding working. One problem I did encounter was that I ended up trying to reconcile three different centre of origins for the co-ordinates. The map data had 0,0 at the top left, the terrain of course has 0,0,0 in the centre and my maths managed to get the A* to read 0,0 at the bottom left, after some profanity meditation I used some quick and dirty and hastily constructed math functions to bring them all into focus, thus as per usual the dev. code was a complete mess, atleast on that score I am consistent lol

 

 

blogentry-12-063191500 1282334307_thumb.jpg

 

 

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.

 

I have uploaded a demo App to the showcase , 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.

1 Comment


Recommended Comments

Excelent stuff MG.

 

I did a waypoint system in Blitz3d a few years back , nothing as advanced as this tho lol.

 

I had a BattleMech walk through a maze from point A-B-A.

It was simple and worked well for what i needed.

 

But your system is much better.

 

Thanks

Gimpy73 ;)

Link to comment
Guest
Add a comment...

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

Facebook Twitter Youtube Github Steam
×
×
  • Create New...