• entries
    154
  • comments
    388
  • views
    163808

Path finding

Sign in to follow this  

458 views

Hello!

I'm back from my short summer trip to Stockholm and Kuressaare. The remainder of my time off will be spent at home (Umea) which means lots of coding. :-)

The last few days I have been contemplating various techniques regarding navigation meshes/waypoints which are handy both for the player character and NPCs. The ideas I have got so far are:

  • Generate the waypoints from the level geometry. This can quickly become a rather large task.


  • Generate the waypoints using a bot which walks around and drops waypoints as it strolls. This will work some what like a blind man with a walking stick trying to figure out his surroundings. The generated mesh might not encompass the entire level. The mesh will also get better and better the longer the bot walks around.


  • Create the mesh in the level editor, i.e. manually place waypoints at specific locations.

  • Right now I am leaning towards the last idea because it is the most simple to implement and I don't think the workload will be that large. When I have done this and got a nice number of waypoints on various locations I will do a ray test between them to see which waypoints connect with each other. This is to generate travelable routes. When this is accomplished I have to figure out the fastest route between different waypoints. I guess something similar to an A* routine should work; I have to investigate this further. Any ideas or comments on this are welcome.

    Right now I have got point and click controls as well as keyboard controls working fairly well. The point and click scheme just needs a path finding algorithm to be implemented.


    Random screenshot :)
    Thanks for reading!

    [edit]
    Oh btw. Just bought my first Mac yesterday, it should arrive sometime next week 8D
    [/edit]
    Sign in to follow this  


    4 Comments


    Recommended Comments

    Nice to see you back! :D Good work on getting both mouse and keyboard controls working, this should please gamers who prefer one or the other.

    Share this comment


    Link to comment
    Looks good, with automatic connections creating waypoints shouldn't be too hard! :) About the bumps you mentioned earlier, since the engine is tile-based can't you create the zones programatically? Something that takes a tile and sees how large a region it can create with it and adjacent tiles, mark tiles "done" and go to next tile. Or maybe the problem will be solved in another way... Have you tried having a collision mesh for each tile that is only slightly bigger than the tile itself?

    Share this comment


    Link to comment
    Quote:
    Original post by Jotaf
    Looks good, with automatic connections creating waypoints shouldn't be too hard! :) About the bumps you mentioned earlier, since the engine is tile-based can't you create the zones programatically? Something that takes a tile and sees how large a region it can create with it and adjacent tiles, mark tiles "done" and go to next tile. Or maybe the problem will be solved in another way... Have you tried having a collision mesh for each tile that is only slightly bigger than the tile itself?


    Thanks! Yes, it is probably possible to create the collision map programmatically but I don't have the knowhow and I'm not willing to put down the work to figure it out. I have also tried to enlarge the tiles but to no help :(

    Share this comment


    Link to comment

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now