Jump to content

On The Right Path, A* Pathfinding In Leadwerks.

Marleys Ghost

1,485 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 ;)

Share this comment


Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

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.

  • Blog Entries

    • By reepblue in reepblue's Blog 5
      There has been some discussion regarding on how to set collision shapes for your models. For 95% of models, you should be building shapes with the Model Viewer as described here. In some cases, the model artist might want a custom shape to be made. In this post, I'll be going over how I import models into Leadwerks, and building custom shapes.
      A few notes first. I use Blender; Blender 2.79b to be exact. I haven't get got the hang of 2.80 and until the new engine's art pipeline is fully online, I don't see a use for it. Leadwerks 4 uses Blinn-Phong rendering so the PBR stuff makes no sense for Leadwerks 4. So for this, I'll be posting screenshots from 2.79b. I should also mentioned that a feature I use in my process isn't present in the Linux build of the editor, which is the collapse tool. (Tools->Collapse). Doing the collapsing via a terminal will cause the models to crash the editor. This seems to be a known bug, as you don't see that feature in the Linux editor.
      Lets say you created a tube model such as this one and you want the player and objects to go into the tube:

      If you tried to make a shape doing the Concave settings, not only it'll be really slow to generate, but the results will not be good. We could make a shape based on the wire frame, but this is a high poly model. What we need to do is make a new mesh, import both models  to the editor, collapse them both, build the shapes for both, and delete the low poly model while making the high poly read the low poly's generated shape.
       
      First to get it out of the way, apply the scale and rotation of the model. This will make Y forward and the scale will be (1,1,1) when you import it into Leadwerks.

       
      Next we need a low poly model.

      This is the same proportions as our high poly. Apply the scale and rotation as the same as the high poly. I also set the max draw time to solid, but this is optional.

      Next, name your High poly and the low poly you're going to be using for the shape appropriately.

      Now lets, export each object as a FBX. For this my high poly is going out as tube.fbx, and my low poly shape is going out as tubeshape.fbx. Here are my export settings:

      If you saved the files in a Leadwerks project while the editor was opened, the editor would have auto convert the files to the .mdl file format. Open the high poly model (tube.fbx) and first collapse it and give it any shape. (Give it a box shape to save time.) you need to assign a shape to the high poly so the mdl file is linked to a phys file. Do the same with the low poly, but you're gonna set the shape as poly mesh.


      Close the model viewer, and then go into the directory where the models are placed. We are now going to delete the box shape of our high poly, and trick it into loading the low poly shape by renaming the shape file of the low poly to be what the previous shape of the high poly was. In other words, we are making tubeshape.phy into tube.phy.
      Before:

      After:

      Notice the time stamp and the size of tubeshape.phy from before being the same as tube.phy in the after screen cap. This should be your end result.

      Notice that the shape isn't sold but now a tube. Objects can go into the tube with no issues. Now, there is another way that uses limb names to generate physics automatically. However, there are a lot of issues I came across using this method such as the shape not being parented to the model when the model moved via physics or a joint. With this way, you have a custom shape, the model is optimized because it doesn't have any children nodes, and everything is clean and tidy!

       
    • By 💎Yue💎 in Dev Log 5
      The prototype is finished, and the mechanics of the game can be given way.  It has established a desert terrain in the form of dunes, this implies that there are no cannons or anything similar, because Leadwerks does not allow a terrain to cast shadows on that same terrain and this looks visually rare.
      So the terrain is like low-slope dunes. On the other hand, I think the texture of the terrain is already the definitive one, with the possibility of changes and suggestions on the part of those involved in this project.
      On the other hand we have taken the model of a habitat of the nasa, which certainly looks very nice. 
      The next steps, are to establish the starting point of the player, this must start near the capsule return to Mars somewhere on the map of 2024 x 2.
      And think about the first thing you should do, repair your suit? Seek a shelter? things like that.  


    • By 💎Yue💎 in The shock absorbers 2
      It's interesting that when you become an expert on something, you're not sparing any effort to see how something works, but rather you're focusing on creating something. And so everything becomes easier.
      At this point of learning there is a glimpse of a low idea of creating a game, but the secret of all this is to keep it simple and to be very clear that a game is a game, and not an exact simulation of the real world. For example anyone who has a low idea of the red planet, will understand no matter the colors of the scene that is a terrain of Mars, even if it is not very real what is transmitted, a game, that's just it.
      At this point I already have an astronaut character who runs from one place to another on a very large 4096 x 4046 terrain that would surely take a long walk. My previous prototype projects involve a vehicle, but I didn't get the best implementation prospect in that time and I always found performance problems in my machine, something that isn't happening with the character controller for a third person player. 
      As always, I think I'm a scavenger looking for game resources, that's where this community exposes links to websites with interesting hd textures, and one or another model searched on the net, but what I've greatly improved is learning to write code, I have a better workflow, writing Lua code focused on the paradigm of object programming.



      Something interesting is the system of putting rocks, all very nice from the point of implementing them. And it works very well with the character controller if you put collision in cube form.
      I've been thinking about implementing a car system, I think it would be necessary in such a large terrain, but I think it's not the time, my previous experience, involves deterioration in performance and something I think is the physics of the car with respect to the terrain and rocks that in the previous project involve deterioration in the fps. Although if you implement a car would have an option would be to remove the rocks, but I prefer not to have a car and if you have rocks. 
       
       
       
       
×
×
  • Create New...