Plan for Xavier "eXoDuS" Amado

A* Pathfinding for Project Raven

A* Pathfinding
Thought I would post a bit about my experience with pathfinding. I've implemented the A* (A-Star) algorithm in script, just for simplicity and rapidness. I'm going to eventually port it all to the engine, but doing it in script allowed me quick testing and fixing without the need of recompiles, setting up classes, etc. In about a couple of hours I had the basic algorithm running, the only problems I had where basically typos or "DOH!s". Since Project Raven is mainly interiors, I didn't justify the work it would take to get my old aiNavGraph working, so I just went with a new class, aiWayPoint, that is placed with the mission editor.
After I had the algorithm working, I needed to actually do something with it, so I tied it into the AIPlayer namespace, since both my npcs and enemies are derived from it. But there was something to be solved, the algorithm calculated the path from a node to a node, so what if the ai player wasn't standing on a node? Ok there came implementation part number one, I created a simple method that is called moveToWayPoint() and takes a node as parameter, what it does is iterate through all nodes, and find the closest and visible node to the ai player, since that node is visible, then the path can be calculated from it, and simply move to the starting node when going through the calculated path. Amazingly it all worked, here's a video from that stage of code, the AI simply walked to the destination node you specify.

www.projectraven.com/ai.avi

Now I wanted to have fun with enemies, so I made something similar to finding the starting node, but to find the node closest to the target, so if the ai is in combat with you, and you start running, when you get out of sight the AI will follow by looking for the closest visible node to you. While doing this I imagined that it wouldn't work very nicely in the situation where you take a path, go back and take another, the ai would move to the end of the path you took first, just to find out you ain't there anymore, so I added a simple thing, I re-calculate the path each time a node is reached, so that the bot is always going towards you. That worked perfectly.

Meanwhile, I noticed that editing the nodes was kinda, a blind job, in theory I knew that it was doing casts, and checking visibility, but what about others? Mappers that don't have a clue how it works, it would be all magic to them, so I decided I needed an editor update. I updated the aiWayPoint class to keep a list of visible nodes in the engine and render green lines between all the visible nodes, also, a new menu was added to the editor called Tools (where I also sticked the Lighting Pack Light editor) which has an option to recalculate the nodes on the fly (I Forgot to mention that the node visibility is calculated on mission load by a separate method that is called, duh, calculateAIWayPointLinks()). While doing this I found a couple of bugs and stuff, but nothing critical, I did have to ghost the aiWayPoints though, until I find a way to shortcircuit the SimSet from the server object to the client so that the lines can be rendered. One of the bugs in my code that I came against was really stupid (tm), I was substracting vectors in script like if it was in code, so I was getting some weird 'shortest' paths :)
Adding these editor lines allowed me to visualize a potential problem with testing visibility the way I was doing it, with no additional check, see for yourself:



The nodes where getting linked through the barrier, they are visible, but the barrier cannot be crossed, DAMN! Fortunately, I thought of an easy solution to my problem. I added a field to the aiWayPoints to control the maxium linking distance, if the distance is greater than that, then nodes won't get linked. So, in places where the nodes might end connecting to something you don't want, you put the nodes that you do want connected closer and set a value for the max distance, works perfectly, and I'm each time more convinced that it was the correct thing to do.



So after merely 3 days of coding (one dedicated to more ai thinking code, like shooting), I have a "functional" AI system. I say functional because it's not perfect of course, it's barebones at the moment, but it makes a great challenge to fight against the bots, they might even come from another way that you didn't even expect them to and get you from behind, so be ware! run like hell!

There are still some things I have in my head to do today, like adding a tick (something like the AIManager in the tge demo) to calculate the path if we couldn't find a path the last time (maybe the player got into a weird place where there were no nodes!). Another thing I want to add is an action field for the nodes, so that if the ai gets to a field with an action field, it could do something, like for example, jump.
I'm also thinking about what to do with real multiplayer bots, this was all done in aiPlayer classes, which are not derived from aiConnection nor have a connection. Obviously multiplayer bots would need extra features, like pickup items, get health if hurting, knowing how to manage different kind of weapons, etc. I'm not sure what to do though, maybe I should just duplicate all the pathFinding code for the aiClient class, but it would have to be inside the engine class, since aiClient uses a normal Player object, and I don't want to stick AI stuff in the Player namespace, for obvious reasons. That's really for the future though, I am focusing on the single player aspects of Project Raven, and it's coming along nicely.

Project Raven
Not sure if many got a chance to see the IOTD since it was up for less than 24 hours, so I'll just talk about it a little bit. Project Raven:Chronicles is a single player FPS game with some RPG aspects, mainly conversations and action driven storyline. I've already coded most of the single player stuff, including a dynamic conversation system, dynamic mission actions and basic inventory/credits. I say basic because we aren't going to do an rpg deep inventory with slots etc, but you do have credit to buy/sell items and a carrying capacity. I say that both the conversation and mission systems are dynamic because they can modify the game world by just calling scripted methods directly, so the NPCs can react differently if you won the mission they encommended to you or if you failed it, also the methods called for each mission on failure or on success can alterate aspects of the home town mission (Neltec City) by changing conversation scripts, opening new places, moving npcs to different locations, etc. The sky (or the bugs) is the limit. Whenever I get time I have plans to implement a conversation editor so the non-scripters don't have to scratch their heads so match for doing something that should be simple like creating conversation scripts.

Life
University sucks, I've started 3 weeks ago the new semester and I already want to go on vacations again, but well, it's what I have to do :/
The big problem is that I don't understand much about what we are seeing and I don't dedicate much of my free time to study or make excercises, so each class I'm a bit more confused. Hope I can get better before the exams!

That's it, hope this plan doesn't fly from the list like my previous one that I doubt anyone read.

Hopefully someone might get some ideas from my pathfinding experience, at least I hope it's useful to someone.

Thanks for reading if you did :)
-Xavier.