Waypoints
Last weekend I finally managed to go visit Sami. For the whole summer I felt that I'd like to spend couple of days at Sami's place, but then there always were other things drawing my attention elsewhere. So this felt like my last holiday trip for the summer, altough the summer is already almost gone. I packed my computer and shaman drum in my car, and after five hours of driving arrived at Sami's thursday evening late. We had sauna and discussed our thoughts and feelings and made plans for the weekend.
I have been working with a pathfinding algorithm for The Unreal World. We'd like to see non-player characters walking the game world in a purposeful manner, heading for a chosen destination, finding their way around lakes and mountains, choosing preffered spots for crossing a river and the like. I know there is a commonly used alogithm called A*, and some of its variations might work pretty well for our purposes. But then, problem solving is the part I like the most in computer programming. So I've been trying to figure out the details by myself. I made a small sand-box environment with a small map with mountains, lakes and rivers on it - and then trying to teach my algorithm to find a way from the left side of the map to the right side. It turned out to be bit more tricky than I thought.
Suppose we are exploring an unknown area, heading to west. Then we would propably walk westwards until we hit an obstacle like a mountain or a lake. Then we could just seek our way around the obstacle. This kind of pathfinding isn't that hard to code, and I actually already have kind of a contour tracing algorithm. But I'd like to make it bit more sophisticated. Supposing that we already knew the area, then we wouldn't be walking in a straight line until hitting an obstacle, but we would already plan a route with some waypoints - placing the waypoints so that we never actually run into the obstacles. If all the obstacles had regular shapes, and there were plenty of free space around each obstacle, a simple algorithm could do the pathfinding. But in the Unreal Wolrd map we have big, irregular lakes, mountains here and there, and rivers with fords. For example, at first my algorithm picked a ford to cross a river, and then when checking for the rest of the route detected an another river and began looking for the best ford to cross it - but as the two rivers were actually branches of one and the same river, and both branches had several fords, my algorithm ended up picking a ford which actually led back to the another side of the first river... I had to spend a good while planning this with pen and paper, trying to think of such a rules which would work in all situations. A good dose of coffee was consumed while figuring this out.
It has been a long time since we last made a piece of music together. So it felt very good to get back to that kind of creative activity. Sami set up a make-shift studio environment, and one by one we recorded different instruments and vocals. To be honest, I don't have a great musical talent. I can play a simple beat with a shaman drum, and play a little of jaw harp, and that's about it. But working together with Sami is so good, as he can combine a primitive punk attitude with a touch of professionalism. For this piece of music we had a nice, simple core idea - or, actually, an inner feeling we wanted to communicate with the music. That serves as a basis for mutual improvisation. Sami is a wizard with audio editing software. While he was editing, I went back to planning and coding the pathfinding algorithm, then returning to the studio for more of recording.
Sunday was a rather warm, sunny day. As Sami's house is next to a lake, I went to swim before driving back home. While driving I was thinking about ways to improve the algorithm. Ah, and I hope I get to visit Sami again later on this autumn.
EDIT: I added a short video footage of Sami playing the kantele. It is here: http://www.enormouselk.com/?q=music-and-videos/sami-playing-kantele
drinking coffee while planning
a sunny day
going swimming
Blog entries
Follow us
Elk News - the email newsletter
Subscribe to the Elk RSS feed, including blog posts, pictures and videos.
Titles only
Full content
Comments aren't included in these feeds. For them you can click the RSS icon in the Recent Comments box.
Our videos at
YouTube
Vimeo
Comments
Sorry I didn't read your post that thoroughly but here's a recursive answer that just popped in my mind. It can be a little slow (or downright wrong) or perhaps not.
Let's call the beginning Beginning and the final goal End.
Do the algorithm first normally from Beginning to End, and number the turning points where you hit an obstacle like Turn_1, Turn_2, etc. to the last turning point Turn_n.
After that calculate the shortest route from Beginning to Turn_n, then Turn_(n-1) and so on until you find a route from Beginning to Turn_k that is shorter than the original route from Beginning to Turn_k. (Or until k = 1 which states there are no shorter routes from Beginning to any of the later turns.)
Now you can consider points Turn_i where i < k as useless goals and ditch them. Or you can think Turn_i as the farthest point where you can aim "directly".
Then go on recursively doing the same from point Turn_k to End and Beginning to Turn_k optimizing the routes from Beginning to Turn_k and from the point Turn_k to End respectively until you find there are no shorter routes. And so on.
correction: Or you can think Turn_k as the farthest point where you can aim "directly".
Oh shit, I found it doesn't work
Did you try with pen and paper, or did you write an actual piece of code to test it?
Anyhow, at first I thought about posting a screenshot about my tests, but maybe I'll do that later on, when I get the algorithm polished a bit (and some bugs fixed).
Neither, I just wrote it here straight from my mind. Today I understood what I was after. My explanation was wrong.
The idea was to find the farthest turning point where you can go straightly. Then find from that point the farthest point where you can go without turning etc. It doesn't necessarily find the shortest route, but now when I think about it, it actually feels rather natural. However, it's pretty likely not what you needed. I'm very sorry for my lack of talent.
In JavaScript-like pseudocode:
First produce a route from beginning to end and put it in a list:
Route = list of turning points with Route[0] as beginning and Route[n] as the end.
function find_straight(a,b) /* returns a straight route (without turns from point a to the point b if there's one, returns NULL if there isn't. That's probably something you're using already. */
/* Here's the new algorithm represented as function */
function straighten_route(Route) {
/* introduce four local variables */
var Beginning = 0
var End = n
var i = 1
var New_route = [] /* an empty list */
/* Set the original beginning as the beginning of a new route */
New_route[0] = Route[0]
/* go on until Beginning has reached the end point of the route */
while (Beginning < n) {
while (find_straight(Route[Beginning],Route[End]) == Null)
{
/* move the end point towards the beginning until a straight route is found */
End = End - 1
}
/* When there is a straight route (remember that there's always a straight one at least to the next turn in the original route) */
/* add it to the new route */
New_route[i] = Route[End]
/* increment i */
i = i + 1
/* set found turn as a new beginning and End back to n */
Beginning = End
End = n
}
/* return the solution */
return New_route
}
Something like that, yes =) Instead of just using A* to find a route around any obstacle, I'm working on different heuristic methods depending on obstacle type. Mountains are simple; despite of their irregular shape you can treat them as regular polygons, and then just go from point to point. But rivers are entirely different; they are easiest to cross on shallow fords, so my algorithm first looks for suitable fords and then picks the best one. And that was the tricky part =) For a moment I thought that maybe I should just drop my heuristics and go for A* as that should always find the route. But after some work with pen and paper I guess I got my heuristic rules working... For the fun of it, I'll post a picture to illustrate the river puzzle. The picture is here: http://www.enormouselk.com/?q=erkkasblog/images/river-puzzle
Pages
Add new comment