It was a valid complaint, mainly because corner navigation was something I hacked in at the last moment and did not have the time to implement a proper solution (such as A*). Luckily, if I don't know how to do something properly then I have no problem in enlisting the help of someone who can. The genius in question for this particular endeavour is Eddie Edwards, a genius of the certifiably annoying damn-why-can't-I-do-the-stuff-that-he-does-effortlessly kind who I was fortunate enough to work with many years ago when I was fresh out of university.
The decision to ask Eddie to help was purely because I knew that in a couple of hours he'd be able to casually implement what probably would have taken me days or weeks of frustration and head-scratching, and sadly I don't have the time to be able to do that. Getting his help saved me time (and by definition money).
So - after a brief explanation of the problem and the provision of some sample data, a C++ program duly arrived in my inbox with the path-finding code implemented and a nice little sample program that demonstrated how the library worked.
 |
| The arrows indicate the direction to travel to reach the target square. |
Converting the code across to C# (because I didn't want to have to go to the effort of packaging it as a library with an Objective-C wrapper, and then having to write a C# export layer for Monotouch) took no more than two or three hours spread out over a couple of days (I do have a day job you know :) ) and the results are as shown below:
 |
| The magenta circles show the rough path to the destination point. |
It's a bit rough around the edges and will require some massaging to integrate fully to produce nice paths, but the hard part is done - the determination of the optimal route from a start point to a destination point when the way is blocked by one or more walls.
 |
| Basic path optimization - removal of intermediate points revealing the most efficient path (magenta line). |
The code as it stands provides a complete path between any two point routed though the center of any intervening tile. It's not particularly memory efficient, as it generates a large lookup table for each level. Currently, my integration of the library provides for this to be generated as each level is loaded. However, this may well be too slow on iOS devices (Eddie himself recommended that I should pre-generate the lookup data and store it to be loaded as required). What I'll probably end up doing is generating it on first play and then cacheing it in the temporary application cache. Data stored in there is only removed when the system runs low on space.
Even though the full path between two target points is generated, it only uses the eight cardinal directions, leading to some sub-optimal paths in wide open spaces. This isn't necessarily a problem. The code already does the hard part of finding a route; in order to avoid some of the pitfalls of the cell-based approach to navigation I can simply post-process the generated path to remove redundant points (as in the image below). That is, I can remove any point along the path that can be connected via a straight line with any other point, provided there is no intervening obstacle. With this, and a couple of other minor tweaks (including increasing the granularity of the route finder so it doesn't aim smack-dab for the center of each cell, but instead tries to find the shortest distance to the next cell) the generated paths should be a lot more realistic and - crucially - our long national nightmare of tricky controls should be over and done with.
 |
| A more complicated route-finding example. |
If I'm feeling particularly clever I may even implement a little path smoothing based on the Catmull-Rom formula, but that's a topic for another day.
No comments:
Post a Comment