welcome guest
login or register

Zen and the Art of Computer Programming

Saturday morning was cloudy. Drinking my morning coffee I was thinking about what to do - there are so many unfinished tasks waiting to be done. And I felt inspired to take a look at the path-finding algorithm. So I sat by the computer and opened the project which had been waiting for months. I had an idea what needs to be done - but after some testing I realized that my idea is not enough and I need some alternative solutions. Reading some articles I went on testing, and by midnight I got it nearly working. Sunday was about the same - I spent most of the day adjusting and debugging the algorithm, and by the midnight there was one tiny bug left. Monday morning I woke up with some ideas for bughunting, and after couple of hours I found the problem and got the algorithm working in a satisfactory way. Of course I needed some breaks during this intensive coding session; I trimmed Raiku's hooves, went walking in the forest, and cooked food outdoors by fire, scooped water from the rainwater bucket to make coffee, and things like that.

Well, I've been slowly working with the path-finding for about two years, so maybe it is time for an overview of the whole process.

The purpose of that algorithm is to enable NPCs to travel the UnReal World map, finding their way around lakes and mountains, crossing rivers at fords to reach their chosen destination. I remember when I started, I only had a vague idea of how it would work - the internet has a plenty of good articles about path-finding, but I tried to figure it out by myself. I managed to code versions which worked in some conditions but failed in more complex situations. But all that work made me more familiar with the basic concepts and problems of the path-finding. After that I turned to reading articles, especially the excellent Amit's A* Pages. The most used path-finding algorithm is called A*, and around those times I also got A* source code from an UrW-player. Based on those I finally had a version of path-finding which works reliably on the big UrW world map. My idea was that with some speed optimization I could first find a step-by-step path by A*, and then post-process that path, converting it to waypoints. Well, but this Saturday I realized that on some cases finding a long path on UrW map might take seven seconds. So, instead of just post-processing a path found by A*, it seemed that I also need some more serious speed optimization.

I already had various ideas for optimization, and most of those ideas involved pre-processing the map. But before trying any of those ideas, I decided to read some articles for insight. Again, I realized that I've learned more about path-finding, so that I could understand some of the more advanced articles. After reading about different optimization methods I decided to try a Jump Point Search method which seemed to be exactly what I had been looking for. The general idea of the method is pretty clever, simple, and efficient. With the help of this article I coded a version of JPS-optimized A*. The initial results were rather promising, so I kept on debugging until I got it properly working. And now, instead of 7 seconds the optimized algorithm found the path in 0.11 seconds. That's impressive! Well, after some testing I found that there are cases where the optimized version doesn't perform any faster than the standard A*, but in those cases the running time is still just fractions of a second. Not only is JPS fast, it also generates a way-point based path. Instead of recording each step tile by tile, it is only interested in such points where the path might turn. (See the picture below, it shows a screenshot of my small test map. The squares with numbers are the ones JPS did check, and the final waypoints are marked by blue circles. Connecting the waypoints we get a path from the origin to the destination. EDIT: for the tile-by-tile approach of the standard A*, see this picture.)

Now, what is funny is that JPS is nearly the same as my initial approach which I tried to figure on my own without reading any articles. And in earlier discussion Ken H already suggested that what I am trying to do is just one variant of optimized A* or something like Dijkstra's algorithm. So, I wasted all these two years looking for a solution which was right front of my nose? Well, but on the other hand, this is just how we humans learn. When I started I was new to the field and unfamiliar with all the basic concepts of path-finding. Therefore I couldn't understand any of the more advanced articles, and I had to spend time working with the basics until I gained enough understanding to comprehend the advanced techniques. Also, I've always felt that reading is more fruitful when I have some questions in my mind - then I can read text to find possible answers. Without questions the answers are just empty words. And for me trying new things is often the best way to identify questions.

I think there is also a limit of how much we can learn in one go. It seems to be that after learning a major thing the brain needs some time to let the new information sink in - this is clearly visible with little kids; they have periods of intensive learning, and after mastering a new skill they are very sleepy and tired for several days. I've also seen this happen with the horses, so I'd guess it is because of the way brains work. Maybe it is related to this, but every time I resumed my work with the algorithm, I felt like building on more solid foundations. As if my understanding of the path finding had been slowly settling in, even when I've not been actively thinking about it. Okay, of course it was not necessary to spend two years with this - I'd guess the whole process could've been completed in matter of two months, if I had been working on it without major gaps. But anyone who has been following by blog knows that I have problems with managing my timetables =)

Yesterday I was thinking that if I get the JPS algorithm working, I'll write a blog entry about the way of the path finding, focusing on those aspects of learning. There was only one bug left, I had no idea of what caused the bug, and I was too tired to debug. Today in the morning I took a closer look, and eventually identified the bug. The problem was a line of code "if (sx<-1) sx-1;" - the compiler doesn't complain about it, it works, but it doesn't do what I thought it should do. And that is because of a pretty simple typo. The line should be "if (sx<-1) sx=-1;" - so there was just that one equals sign missing. During hours and days of coding I had seen that line of codes so many times, without ever realizing that there is "=" missing. Since I didn't know what exactly was wrong, I made the algorithm to write all kinds of debugging information into a text file. Reading that file I found that in some cases the variable sx had value -4, when it should have only values -1,0 or 1. So, I went back browsing the code, looking for the cause of this error. And there it was, a rather simple error in just one line of code. I only spotted the error now when I knew what I was looking for - before this I had just assumed that this line of code is very simple and does what it should do. This reminded me of a text I wrote some 25 years ago. It was titled "Zen and the art of computer programming." I'm afraid that the original text is lost in the cyberspace, but I think I still remember the central points.

Before you start coding, meditate to clear your mind. Forget about the timetables, forget all the goals, and just concentrate at the moment at hand. A hurried, nervous mind will result in messy code.

If there is an error in your code, it can be of two reasons. Either the code is doing what you intended, but your solution doesn't work. Or there can be a bug in the code, meaning that the code doesn't do what you thought it should do. In the first case - clear your mind as peaceful mind is more creative to find new solutions. In the second case - clear your mind as peaceful mind is better able to see lines of code as they are, instead of reading them the way you think you wrote them.

Practice these with the art of computer programming, and you'll find the same principles working in other areas of life, too. Clear your mind, see the things the way they are instead of assuming them to be the way you think they are.

Waypoints for a path from the blue square to the red square
Waypoints for a path from the blue square to the red square
401 users have voted.


Zen and the art of computer programming. You wrote it when you was 15? You had blog?

15 or 16, around those years, can't remember exactly. The text wasn't a blog, more like a forum post at a BBS which Sami hosted. I don't remember if the text was "published" elsewhere - since it was just a plain text file on my home computer, I might have posted it on some other discussion boards, too. At those times an internet access wasn't yet common, and people used those smaller BBS systems.

EDIT: I was left thinking about this. I really can't remember exactly - I wrote that text when I was something in between 15 and 20 =) I remember the idea of the text, but I can't remember where or when I wrote it. It is funny how once those times were a vivid reality almost painfully present in full detail. And now they've faded into the merciful haze of past memories. Then, on the other hand, I've never been good with linear time. Maybe this would make a topic for a separate blog entry, let's see =)

I'm surprised that the original text can't be found anymore. I actually remember reading it, on the web, sometime in the 1990s.

By original text you are referring to "Zen and the art of computer programming" by Erkka Lehmus ? If so, then I'm surprised that there is someone around who remembers reading the text. As, when I wrote it, I didn't have an internet access. Also, I wrote the text in Finnish, and posted it on the discussion forums of Sami's BBS. So, the potential audience wasn't that big =)


Add new comment

Please reply with a single word.
Fill in the blank.