Below is preliminary proof that my AI Pathfinding algorithm works. I put it into a scrolling box so that it isn't ungainly large. It is abbreviated output from Hack Mars, my Video Game. Read more on that below. But to decipher my algorithm's output, here are some clues.
PFPath = Portal::findPath()
RFPath = Room::findPath()
DFPath = Door::findPath()
The line that looks like "39.4->39.2->39.10->39.6->39.8->" is a list of rooms that my NPC will walk through.
PGPath = Portal::getPath()
RGPath = Room::getPath()
The last group of lines are points that the NPC will pass through. The picture for today shows squares where these points are placed. I temporarily made the path draw on top of everything (glDisable(GL_DEPTH_TEST);) so that it is extra visible. I also increased the field of view to ~140 degrees so that the camera can see the entire path. The path goes from the bedroom, up the stairs, around the corner, and into the kitchen. It's pretty sweet, right? So for a long time, first-person shooters (FPS) as well as many other games have worked on systems to do artificially intelligent pathfinding. I found a way to do it. See below.

PFPath: Room 4->8, 5 levels.
RFPath: Room 4->8, 5 levels.
DFPath: Room 4->8, 4 levels.
RFPath: Room 2->8, 4 levels.
DFPath: Room 2->8, 3 levels.
RFPath: Room 4->8, 3 levels.
DFPath: Room 2->8, 3 levels.
RFPath: Room 5->8, 3 levels.
DFPath: Room 5->8, 2 levels.
RFPath: Room 2->8, 2 levels.
DFPath: Room 2->8, 3 levels.
RFPath: Room 1->8, 3 levels.
DFPath: Room 1->8, 2 levels.
RFPath: Room 2->8, 2 levels.
DFPath: Room 2->8, 3 levels.
RFPath: Room 3->8, 3 levels.
DFPath: Room 3->8, 2 levels.
RFPath: Room 2->8, 2 levels.
DFPath: Room 2->8, 3 levels.
RFPath: Room 10->8, 3 levels.
DFPath: Room 10->8, 2 levels.
RFPath: Room 2->8, 2 levels.
DFPath: Room 10->8, 2 levels.
RFPath: Room 6->8, 2 levels.
DFPath: Room 6->8, 1 levels.
RFPath: Room 8->8, 1 levels.
DFPath: Room 6->8, 0 levels.
RFPath: Room 9->8, 0 levels.
DFPath: Room 6->8, 0 levels.
RFPath: Room 10->8, 0 levels.
DFPath: Room 6->8, 0 levels.
RFPath: Room 7->8, 0 levels.
39.4->39.2->39.10->39.6->39.8->
PGPath
RGPath: Room 39.4--[39.2]-->39.10.
RGPath: Door 39.4->39.10.
RGPath: Path 2.
RGPath: Path 6.
RGPath: Path 0.
RGPath: Path 1.
RGPath: Room 39.2--[39.10]-->39.6.
RGPath: Door 39.2->39.6.
RGPath: Path 1.
RGPath: Room 39.10--[39.6]-->39.8.
RGPath: Door 39.10->39.8.
RGPath: Path 1.
RGPath: Path 3.
RGPath: Path 6.
RGPath: Path 5.
RGPath: Path 7.
RGPath: Path 4.

-5.85707 -1.51145 43.0833
-6.19277 -1.51145 43.466
-6.19309 -1.51145 43.8854
-6.19328 -1.51145 44.3048
-6.2296 -0.752594 45.2361
-6.20489 0.0062926 46.1676
-6.20527 0.00511837 46.602
-6.67266 0.00520935 46.6022
-7.09363 0.00520935 46.2923
-7.14902 0.00533307 46.153
-7.14947 0.00520941 45.7211
-7.20854 0.00409584 44.5062
-7.20878 0.00409579 43.738

My portal system and a very interesting idea that worked out over a few months during a Physics course. The portal system is very simple. It's fundamentally 2D, but it can works with ramps to do full 3D. I make rooms out of triangles in a 3d editor (Milkshape 3D). These rooms are connected by door triangles. It is also useful to use separate meshes (for prefab purposes), so I have a system of interconnecting doors which works well (even if it's slightly obsfucated).

So the pathfinding is pretty simple: go from room to room through doors. So room 4 (bedroom) is connected to room 8 (kitchen) via room 2 (hallway), room 10 (ramp), and room 6 (hallway). It simply takes a few loops to solve this. It's actually very fast. You can see how many function calls it requires below (32). It's also possible to optimize it further.

So once I have a list of rooms I have to go through, how do I go through them? If I simply drew a line from the midpoint of one room to the midpoint of another, it would go through walls. But if I checked for walls, it would not be real-time (>10 fps). Well, the solution is actually very cool. I take each room and check for the beginning door. Then I check the other side of the triangle that the door is on. I then check the adjacent triangle and so on until I have found the end door. It's quite fast on simple rooms. Then I just find the midpoint of the edge of the triangle to pick points on the path. So the only requirement is that the rooms are simple which is an easy requirement to meet (rooms are really just squares and T shapes).

I plan to open up the source when I release Hack Mars. I'd be happy to open the source now, but not many people would find it useful. It's beta code right now. It has bugs. The old AltSci3D Manga Director source code is up, but it's about 6 months old or so. It doesn't even use Python, which is the main part of Hack Mars. But now that I've given you a pretty good idea of the system, it should explain just how deep the AI pathfinding technology for Hack Mars goes. Which leads into the next section.

Hack Mars will use pathfinding AI extensively considering ~1000 NPCs will roam Mars and play important parts in the role playing game (RPG). RPGs often dispense with NPC pathfinding AI and just glue merchants to their place. I find that efficient, but lacking in realism. At very least the merchants should sleep at night. If their bed is in their home, there should be no problem allowing them to lock the door and go to bed at night (inconvenient for gameplay as it may be). Monsters usually have very simple AI like search and destroy, patrol, and flee. Some NPCs in RPGs are allowed partial monster AI such as seek and destroy as well as patrol. While that lends a bit of realism, it gives the NPCs one or two of three possible brains: sell, talk about quests, or kill on sight. So what do I propose? I propose Hack Mars should have workers that go to work at 9 AM and go home at 5 PM. Students that go to school at 8 AM and work an internship at 2 PM, and go home at 6 PM. UN PKs that patrol one area, eat lunch, respond to their radio, go to HQ, and live like humans instead of monsters. I believe that such AI can give Hack Mars the realism and story that will allow it to distance itself from other games. Hack Mars is about human interaction, not murder.

So how to compare? Half-Life was described as the most realistic FPS game due to it's extensive AI. But really it had very limited AI: follow, seek, patrol, and attack. Their ability to switch on cue was very simple. Friendlies were helpful, but not that much. Human enemies in Half-Life seeked cover when attacked. They would swarm in groups under certain circumstances which was kinda cool. But the end it could not facilitate a story where the solution involved complex communication or teamwork.

Better games through AI. Now that's radical.

Permalink