Noise optimization
I've been experimenting with the path finding program. At the moment I'm working with the classical A* algorithm, which analyzes the map until it find a way from origin to destination. For those who are not familiar with the way computers deal with information, let's first take a quick look at the basics. In a way, a map of the area is divided into small "tiles", each tile representing a square area of terrain. On UrW map the basic tile is 100*100 metres of terrain, and each tile is marked like "water, forest, mountain" etc. So, now the A* algorithm starts from the tile at the origin, and tile by tile tries to go towards the destination. If it encounters a blocked tile (like a lake or a mountain), it goes on to scan neighbouring tiles, until it finds a way around the obstacle. And that "scanning of neighbouring tiles" is powered by an algorithm, which estimates that which tile should be scanned next. Essentially, to make the path finding faster means to make that estimation part both better and faster. The less tiles the algorithm has to scan, the faster it find the way.
Now, a major difference to human perception is that a computer doesn't understand "areas", "regions", or "contours". For a human looking at a map it is immediately evident that "there is a lake, it contours are about those, and a way around goes there or there." - but a computer has just a huge array of separate "tiles". If I want the computer to figure out the contours of a given lake, the simpl way is to scan the map tile by tile, finding if a certain water tile is neighboured by another water tiles - that would finally lead to some sort of representation of "that lake", ie. a list of water tiles next to each otherd, bordered by non-water tiles. Since I learned computer programming in my teenage years, I've been interested in different ways of modelling "areas" and "connections" and "relationships between areas / objects / processes". But I'm not a pro on that field - I bet there has been a lot of advanced studies on those questions, but I've just been too lazy to study.
So, lacking computer models of "that obstacle", I'm left with optimizing the algorithm which scans the path tile by tile. To compare different ways of optimization I made a program which runs the path finding twenty times, tracking how many milliseconds it takes to find the path, and then calculates the average time. (Yup, even with the exact same code the amount of time varies from a run to another - I think it is related to other processes running on the computer. So, sometimes I'm lucky and other processes are demanding minimun processor time, and my algorithm runs faster. Sometimes it takes slightly longer. The difference is minimal, but still it is there, so instead of a single run I wanted to do 20 runs and count the average.) I started with a clean mathematical model, which gives relative weights of 100 to 140 per tile travelled. That model gave me an average of 0.283 seconds to find a given path. Then, on the exact same map, exact same origin and destination I tried adding a little random noise to the algorithm. Now, the base value is calculated just as before, but a random number ranging from 0 to 9 is added to the mathematically calculated base value. The average time of performance dropped to 0.219 seconds, and the path looks better and more natural. Why is this? How can a small random noise make an algorithm run faster? Well, I'll return to this question, but let us first step into the world of movies.
Have I ever told that I like the first two movies of the Aliens saga? Especially because they are able to discuss deep philosophical themes without rubbing them to your face. The dialog rolls on, the action gets going, and after the thrill you are left with themes to ponder. The first movie features science officer Ash praising The Alien as the pefrect life form "unclouded by conscience, remorse, or delusions of morality." At that point of the film it is already clear that Ash itself isn't a human but an android following a program with no compassion for fellow crew members. This echoes a classical assumption in Western thinking - cold hard logic and rationality are seen as the most efficient and "pure" form of thinking and behaviour, whereas emotions and feelings are only muddy waters obscuring the clarity of thought, leading to faulty decisions and inefficient performance. Well, the second film, "Aliens", takes a good look at this theme. In the beginnig we have traumatized Ripley, terrorized by nightmares, unable to pursue her professional careed due to issues with The Company. Finally Ripley agrees to return to face the aliens once more, this time accompanied with an unit of well-trained Colonial Marines packing some serious firepower. So, at this point it is "non-humane killing beast Alien versus armed and trained men, a tough female warrior, and Ripley with no military training." The Marines seem pretty confident about their victory, they go with an attitude of "we go there and wipe them out, simple as that." But what happens? This time they are not betrayed by an android following non-humane programming. But the traitor is The Company representative Carter J. Burke, who is willing to sacrifice the rest of the crew for private profit (as The Company has promised a huge bonus for bringing back a sample of Alien, which they hope to use as research material for developing new weaponry). This time Ripley compares Burke to Aliens, picturing Burke as worse beast - because The Aliens are loyal to their kind. Afer all, The Alien Queen is just protecting her offspring, and Alien soldiers are protecting their hive. But Burke, as a human, doesn't care about protecting his fellows, if he can exchange human lives for huge private profit... So, in the end we have Alien Queen versus Ripley who has regained her self-confidence. Both the females have protective feelings towards their offspring (either biological or adopted), and it is exactly this motherlike protectiveness, which fuels their rage in a physical battle. Winning the fight Ripley shows that having morality and feelings of love and caring is not a sign of beign "less than perfect". So, we must ask: why should we see emotionality as a sign of weakness? Why do we think that "being rational and efficient" would necessarily mean "being cold and non-emotional?"
In some of the previous posts I've already written quite a length about "emotional pre-processing" and things like that. Maybe it is about time to add more meat on the bones of those earlier ponderings. There are some empirical studies of patiens with a spesific brain damage. Those patients experience a total disconnection of emotional evaluation and rational thinking. So, does it mean that they become highly logical, extremely efficient andoid-like superworkers, who just choose a goal, select the best means to achieve the goal, and then just carry on implementing their plan "unclouded by conscience, remorse, or delusions of morality"? Nope. Making decisions becomes extremely difficult for them, and they easily become indifferent and unfocused. The problem is that without any emotional pre-processing they just see a awfully lot of equal options, and rationally evaluating the pros and cons of each option takes a lot of time and often yields no definite answers. I think many of us have experience those situations, when we find it very hard to choose among several options, as it is a case of "option A feels like the best one, but then on the other hand option A has these problems, whereas option B doesn't have any of those problems, but then on the other hand there are other problems with B, and C seems harder to do but comes with less downsides, but there is a slight risk of total failure with C, but then on the other hand maybe I should still choose A because..." and so on, good and bad sides always balancing each other out, so that we are left with just nearly equal options... Sometimes this kind of situations are portrayed as a "conflict between head and heart - my emotions say A, but my rationality says B". But I'd guess that most often it is actually a case of different emotional motives conflicting with each other.
So, what I mean is that emotionality and emotional processing of information might actually be not only a necessary but a highly beneficial feature of human mind. Emotional pre-processing helps us make decisions quickly. And emotions like "morality and conscience" help us to create and to maintain networks of co-operation, running with smooth group behavior. Which brings us back to the path finding algorithm. The pure mathematical model sometimes encounters situations where it has like 100 tiles to scan, each of them having the exact same relative weigh value (say, for example, they all are assigned a value of 600). So, out of thousands of alternatives the algorithm has picked a hundred of most likely candidates, and then goes on examining each of them one by one. Highly rational and effective? Well, but with a modest random noise added that list of 100 tiles now has values ranging from 600 to 609 - which gives us only about 10 tiles with the exact value of 600. So, instead of scanning all the 100 tiles in the list, the algorith randomly chooses those ten, and goes on examining those. And so on - the resulting path might not be perfect, there are some sidesteps and smooth curves - but the path is good enough, and faster to find.
A path finding with random noise runs about 22% faster than a path finding with strict and clear mathematical model. If a mere random noise optimization gives this good results, then what would do more sophisticated heuristics? In a way I find this also capturing something essential about my personal probelms with managing my timetables. The goal is clear; I want to organize my working hours better so that I would have more time to regularly work with UrW development. So, why do I so often fail with it? It seems to be just another symptom of that freeze-reaction I've mentioned before. As, in many practical situations it feels like a lot of my internal bodily and emotional signals are numbed, I feel like wandering in thick mist, using only my rationality to navigate. And if the situations demands an immediate response - a customer calls, I pick the phone, the customer asks for a time for a massage, I quickly scan my calendar and pick a free time - I might often fail with making that decision, because I feel indifferent inside. That's like a list of 100 options, and without any emotional pre-processing my rational mind is not able to calculate that fast, and instead just picks the first alternative in the list (ie. booking the customer with a first easily available time I spot in my calendar). I've been emulating "the emotional pre-processing" by taking an advance look at my calendar, trying to make clear markings for each day, like "no customers at all for this day", or "this day you can book customers only after 2pm but not before, because the prior day you've been working a long day till late evening" - but even with those markings I sometimes fail - my eyes see the markings, my rational mind knows what they mean, but somehow they carry no emotional significance. And the rational mind always sees so many pros and cons, for example violating my own markings is not a good thing to do, but then on the other hand working more means accumulating more money, and more money means that later on I can have even more completely free days concentrating on programming. So, violating my own pre-processing can be rationally justified as serving the ultimate goal... To me it seems that the rational mind actually isn't that effective in managing my timetables. What I would really need is defusing the remains of that freeze-reaction.
Comments
That's interesting, the path with random noise added to the weights looks much more optimal than straight up a*... a* moves north first then starts to skirt around the large lake system while the noise added algorithm just beelines for the hook turn around the lakes. Now, just to keep this in perspective, a person who did not know the lay of the land would do far worse than either a* or your modification. I would test your method on more varieties of terrain to see how it performs. If it's consistent you could use it to path-find for entities that possess knowledge of the lay of the land and use less optimal methods for entities that don't know anything about the terrain they are traveling over.
Well, tinkering with pure mathematical heuristics of A* it should be possible to make it find always the best path, ie. the shortest route. But here I was aiming at optimizing speed.
Theoretically speaking all this is so very interesting. For example, instead of mere random noise there are other ways of emulating "a hunch" when choosing which tile to explore next. UrW random world generator assigns an internal height value for each tile on the big world map. And then every tile with height value of say 60 or less is converted to a water tile. Now, using that information it should be possible to make the A* to avoid going too much downhill. If the origin is at height level 120 and destination is at level 160, then the algorithm would prefer tiles in between those values, unwilling to go much higher or lower. That kind of simple heuristic should make paths curving around lake areas - often finding a longer path but being faster. Maybe I can test that one day =)
Well, but for actual use in UrW, I'd guess it is safe to assume that all the NPC's travelling the world map are already somewhat familiar with the surroundings. (But of course for the sake of realism we also need another algorithm for situations where an explorer is exploring unknown terrain). We have been thinking about post-processing the path so that it will be stored as a handful of waypoints. But I'd guess we will also use some degree of pre-processing to speed up the pathfinding. I'll write more about this when I get back to working with this =)
PS. More of "work-in-progress" thoughts; http://www.enormouselk.com/?q=erkkasblog/images/28th-march-2015
Pages
Add new comment