Singularity Update 10

Changelog

-Command-line arguments now use more standard syntax. -Added a menu entry to mark all viewed items as read. -Singularity now asks for confirmation before deleting feeds. -Added settings for how attachments are handled, but they don't do anything yet. -Added an 'about' dialog to display information about singularity.

Well, as you can see I'm back! Unfortunately, this update is mostly full of simple, boring stuff. I wanted some lighter tasks to get myself back intothe groove of things, so I knocked off a few simple features from the v0.2 list. My original goal was to release by the end of the year, but it's hard to tell if that'll happen. Assuming I work my butt off and nothing truly awful happens, I'm probably ok, but you can never know with these things. I'm glad that my estimate was in the right general ballpark though. So far, I'm pretty happy with the progress I've made on the project, although I'll probably stop updating for a long while after 0.2 hits.

300 (Teapots)

Ever wondered what a gang of 300 mobile teapots looks like?

...No?

Well, too bad:

Apparently, 300 teapots

Now, as funny as it would be to just leave this image here without context, I think I should explain what's going on here.

This strange scene is from a class project for my recently completed AI programming course. This was actually the midterm, but I was too busy to share it at the time. With the semster over, though, I can finally write again!

Background

Like any good course on game AI, this one featured a section on pathfinding. Our instructor gave us a basic rundown of Dijkstra's Algorithm and A*, then let us group up and research some more advanced techniques. With Peter off doing who-knows-what, I paired up with Johnathan O'malia, a pretty great coder who I met in the class.

The Project

For our main technique, we looked at using navigation meshes to generate pathfinding graphs from 3D environments. To create the navmesh, we used Recast, a peice of open-source middleware. If you look below, you can see screenshots showing the test mesh with and without the pathfinding graph displayed: Before... ...and after! Now, if you've worked with navigation meshes before you might find the result overcomplicated. You'd be right to think that, as the resulting graph is actually a subdivided version of the original navmesh. We did this so that we could work with a relatively simple node array, rather than pathfinding with the mesh itself. Because of that, we nedded to subdivide the mesh to produce some in-between nodes that would allow us to produce straighter, more direct paths.

The Teapots

As you may know,the teapot model in our project is an old favorite known as the 'Utah Teapot.' If you know what it is, it should be pretty obvious why it was used. However, the fun part comes when you consider the context. The teapots are AI agents that need to path to a specific location, in our case the camera, and so we ended up with the strange situation of being followed by a group of strangely intelligent teapots! The nature of the assignment also lead to a few odd visuals, like these teapot centipedes:   I especially like this image So, uh..... yeah. Teapots! The red lines that you can see in the first image denote the paths calculated by the teapots. Johnathan added some sort of smoothing function to the paths, and I've got to say that the result is quite nice in action! Another thing that you might notice is the rudimentary lighting engine. I wrote that part, and expanded further it in a later project, but that's a topic for later. I'll leave you with an aerial view of the map, with only the paths shown: As you can see, the teapots have just finished their long march to the top

Really Fast Pathfinding, an Assignment

As you probably know at this point, I'm currently a college student majoring in Game Programming. As this semester wraps up, I have to research and explain an AI programming technique here for my final assignment. In this post, I'll be explaining how to use jump points to make a ridiculously fast grid pathfinder.

Note: This tutorial expects that you already understand the basics of the A* pathfinding algorithm. If you don't know it, I recommend looking here. It's the best and easiest resource on the subject that I know of.

 The Problem:

When pathfinding speed can often arise as an issue. A*, the most common pathfinding algorithm, can be fairly slow in numerous cases, especially when dealing with large open spaces. Obviously, this means that games can put A* into it's worst cases on a pretty regular basis. For this reason, a huge number of techniques have sprung up to try and improve A*'s speed when dealing with such areas. I'm going to be talking about one such technique: The Jump-Point Search, or JPS for short.

Turns out, both of these are of equal length.

JPS is based on  the notion of path symmetry, where multiple similar paths have the same length. This mostly occurs when dealing with grids. With A*, hitting a wall or corner often leads to unnecessarily checking a large number of tiles. Thus, the goal is to only check tiles that are important, and ignore the all of the empty space. JPS does just that, by turning small steps into huge leaps.

Introducing JPS

JPS is a surprisingly simple technique that only alters one stage of the process. When the time comes to get the neighors of the last checked node, JPS makes each neighbor 'jump' before adding it. To do this, JPS makes the neighbor move away from the original node until it reaches a turn of some kind. How does it do that? That's the interesting part.

A diagram from the original paper, demonstrating how JPS ignores neighbors. Anything greyed out can easily be reached by the original node, and is ignored.

When 'jumping', JPS acts under the assumption that most of a nodes neighbors can be reached by the original node, and so it ignores them. If a jumping node runs directly into a wall, it returns nothing, since that particular line contains nothing useful.
To find walls, JPS does two things. First, it checks certain neighbors for walls. As you can see in the above diagram, walls can only block out a node's neghbors from the original position if the node is moving orthogonally, and they are perpendicular to its movement, or the node is moving diagonally, and the wall is slightly behind it.

The horizontal and vertical jumps, as illustrated by the original paper. Dashed lines indicate a failed jump.

The second check is only made if a node is moving diagonally. To ensure that a far off but accessible turn isn't missed, the node sends out two more node 'jumps' on its vertical and horizontal movement.
When one of these cases is found, the node stops and is added to the list. Also, if the endpoint is found at any point then that gets added as well. This effectively leaves the list of nodes to check with only potentially important ones, leaving out the filler.

So, Why Care?

There's one simple reason to care about JPS: it's better than regular A*. It's proven to still find the shortest path, it requires no additional preprocessing, and best of all, it's pretty much always faster. The paper mentiona that their worst case had JPS finding paths at around 3 times the speed of A*, and their best had JPS doing so 30x faster. No, the 0 is not a typo. That's immense! I've implemented my own version, and it's still a rather buggy, but still usually outperforms A* by a noticeable margin. In other words, I see no downside to using this in any game that ca, on whatever platform you want. One thing to note is that this only works on on grid-based graphs. If your pathfinding graph is more freeform, then the technique won't be of much use. Of course, at that point you can probably just add your own optimizations anyway.

My Attempt

I've written my own A*/JPS implementation in C++ using Drunkard's Walk-generated random areas and ncurses output. Here's how it looks(Highlighting added after):

Red areas indicate where nodes have been checked/added to the open list. Note that the full path is quite long, so most of it is missing. Rest assured that it's pretty much just like this the whole way.

As you can see, JPS changes things quite a bit. One thing to note is that a JPS path will mostly only have nodes at turns, so you'll have to fill paths in if you plan to snap movement to the grid. I decided not to other in my demo, as I don't really need to do anything more with the path. I've decided not to include my demo here, as it's fully exclusive to Linux, poorly coded, lacks comments entirely, and features a a very draconian vim-like interface that would make most normal people uncomfortable. If you really want it, though, feel free to send me an email or comment, and I'll be happy to make it available on an individual basis, source and all.


Well, that's it. I find JPS a bit difficult to explain, so I hope I've done a decent job of it. I recommend taking a look at the original paper, linked below, if you're confused. It contains psuedocode for the entire jump function, which makes implementation easier. I should warn you now, though, that the language is very academic, so it can be a pain to read. My third reference below has an online demo, so if you just want to see the algorithm run without making your own implementation you should head there.


References:

1. http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/viewFile/5396/5212 - This is the original article that describes the JPS technique. A very useful source of information, if you can decipher the academic writing.
2. http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/ - This is where I first encountered JPS. I was researching some things for another project(I'll be posting about that one later), and I ran into this. It looked like a cool technique, so I bookmarked it for later use. This particular resource talks about another technique as well, but doesn't go too in-depth into either.
3. http://zerowidth.com/2013/05/05/jump-point-search-explained.html - Another resource that I used to help me figure out what was going on in the paper. It has some useful diagrams and an interactive demo, making it a really great reference.