Mark Sachs (ksleet) wrote,
Mark Sachs

  • Mood:
  • Music:


So I finally had some spare time to work on Neon Galaxy and actually got pathing to work!

The first thing to do is that we have to construct a simplified representation of the map, because it would be hard to make the computer able to handle every fiddly little detail of the environment, even in a simple 2D world like this. Fortunately, constructing that representation -- the graph, that is -- is easy because of the way I generate the map. As I attach corridors and rooms, I just have to keep track of the exits I'm creating from each chamber, and then tell each exit about the exits in the two adjacent rooms. And bingo, we have a graph (the pink lines) connecting all exits in the map.

In principle it should now be possible for an AI to travel anywhere on this map by finding the nodes closest to its start and end points, then getting onto the node graph and riding it to its destination. However, we do still have to actually figure out the shortest path along the graph to the destination. Fortunately, this is a well-trodden path in computer science. I was able to essentially do a monkey-see-monkey-do implementation of the famous A* search algorithm and no one was more surprised than me when it pretty much just worked out of the box! As you can see from the screenshot, the pink path leads from the player's current location back to the center of the starting room. I can maneuver anywhere I want on the map and the path will be constantly updated, indicating that A* is doing its job.

Now, there are certain improvements that need to be made; most obviously, there have to be more path nodes. As you can see, the path to the center of the starting room seemingly detours over to the southern exit -- that's because the closest path node to the center is at the southern exit. A node in the center of the room might help (though in practice, any AI trying to follow this path should just do some raycasts to identify the farthest-away node on the path it can directly see, and just go straight there.) As well, anybody who actually tried following that path would find themselves scraping against the walls of the hallways half the time. Some intermediate nodes to allow more graceful maneuvering would be a big help here.

As a bonus, I reworked the exit representation in the map to get this working, so now if I want to (say) implement doors that open and close, it's a lot easier to do so.

I'm not quite sure what I should work on next! I guess I still should improve the AI locomotion and replace the current hacks with a proper movement system, but I'm not sure where to go after that. Although... hmm... Doors, huh. That might be fun.
Tags: neon galaxy
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.