1UP: Okay. God of War?

Hideki Kamiya: My impression is that it’s very carefully made, the details are all carefully made. Devil May Cry was a bit rough, but I think that there’s no roughness in God of War. I think that it’s very well-made. So there’s like a wall for your imagination or ideas, and when you’re actually creating something, you don’t even see the wall. But with GOW, I felt like I saw beyond the wall. So the GOW dev team’s imagination and their ideas were like… beyond. That’s something else that struck me. And also, I feel a bit bad about talking like somebody who is evaluating a game. But I felt like they created the game in a very good way which managed to bring in the users, they gave you a huge impactful feeling right in the beginning, and just drew you into the game. So I’m very impressed that they made the game like that.

Yusuke Hashimoto: The level of the game was very high in general. So the things that you see in the game are things that you can’t even imagine. The imagination is one step ahead of you.

Hideki Kamiya: In this game, they were using a camera system that was on rails. The camera follows the character like they’re on rail tracks. And so it makes the game really easy to play, and of course I was impressed by that. And there were people around me who were like, “Oh, you should use that camera.” But it’s not something that you can easily do. To create that kind of a system, you have to pile up a lot of technology, and study a lot, and research a lot, to be able to make a camera system like that. I was like “Okay, you guys appreciate the technology, but it’s not that easy. Everything in the game is not easy to make.” These guys were really serious about the creation, and they put in a lot of effort in it, and that’s why that game came out so well. So yeah, I played GOW2 and the PSP version, and I feel that they were very well-made.

Enter Akers’ algorithm. With a single RGBA8 buffer we can now do not just 4 problems in parallel, but 16 problems in parallel (as each only requires 2 out of 8 bits available). Then add MRTs on top of that for even more parallelization.

Always explore options. Always know multiple algorithms. Other reasons to care left as an exercise for the reader.

This approach is slow and memory hungry in comparison to normal methods. Please profile it.

The bit (no pun intended) I was missing was that on arrival of the goal cell during the flood-fill stage, you don’t need any previous path information; just knowing the previous depth is actually good enough, because knowing any 2 bits in the sequence uniquely determines your spot in the sequence.

Anyways, cool algorithm!

Sure it does, you do exactly the same thing in both algorithms! For Akers’ algorithm you start at the goal (which had a value of 1), and then go, in sequence, to successive neighboring squares with the following values: 1, 0, 0, 1, 1, 0, 0, ….

The beauty of Akers’ encoding is that following the sequence backwards (based on wherever in the sequence you were when you reached the goal) will make you arrive at the start every time!

I don’t believe just passing in the depth is sufficient, however.

Both algorithms, as described above, assume a 4-connected neighborhood. If you want to include paths that use diagonal moves then you need to also flood-fill diagonally during the search phase of the algorithm, otherwise you won’t necessarily reach the goal from start. Consider e.g. a chess board where all black squares are obstacles and start and goal are at opposite sides of the board on white squares (at A8 and H1); here there exists a path (along the diagonal), but the 4-connected flood-fill cannot number any squares.

Lee’s algorithm trivially adjusts to diagonal moves, Akers’ might too (haven’t thought about it).