I entered the contest (see icfp 2003) to see if TCL was up to the task of other language. Although the challenge is aimed at function langauges, any language can be used in the contest.
Due to an unfortunate set of circumstances I did not receive the contest start notification until a day after the start. I almost did not take up the challenge because of this , but eventually decided to as an academic exercise.
I had only Two days to write the code and did not get it completely finished before the deadline. I achieved the following:
I carried on coding up until I hade spent the alloted time on the contest. The current state of the code and this documentation was the result.
The task description can be found here
The archive of the code that was created can be found here.
Due to the presure of a late start I did not look at the example data and started from the route finding code. This in hindsight was a mistake as this was not an important part of getting a result.
Once I moved onto the simulator I saw that it was just as easy to create the route by hand and get the car to try and follow the manually created route. Had I started with this end I could have solved some of the tracks in the time I had.
Because iterative methods in Tcl become impractical due to the time required to iterate over the millions of combinations , a simpler approach was used based in the Sober Sailer analogy.
Unlike the drunken sailor we work purposefully (but no necessarily optimally) towards the goal.
We start at the start and cast rays out in a given direction.
We then test for collision. If none we continue from the end of the ray in the same direction.
When we collide we backup and then change direction slightly and try again. If a route cannot proceed in any direction, or it crosses our path , we backtrack in the path and try another direction.
This approach quickly finds a way from start to end. It does not however compute the optimal path, not does it construct the path in a way that matches the dynamics of the car. This means that there is no gaurentee that the car can actually drive the path at speed.
Rather than maintaining an associative array of objects and bounding boxes, the objects were drawn on a canvas.
Since the canvas coordinates are floating point values, they can be used directly without having to be mapped between different geometry spaces.
There are problems due to round off errors accumulating due to the testing system using fixed point arithmetic only.
Because of the number of points was too much for TCL to handle efficiently,
the images were rasterised into linesegments. While only two types of points existed, go, no go, there could have been a small number of lines used to represent them.
However visually the nogo areas were coloured so they we kept as seperate entities so they could be rendered as intended.
A problem was found when attempting to test if a proposed travel direction intersected a line. This was caused by limits in precision.
The solution to this was to rasterize the image in both the x and y directions. This ensured that there was always one line segment out of the three that was not coincident so the intersection test would be reliable.
A better approach would have been to use a flood fill to obtain the bounding box of an area and then represent this with a polygon object.
When casting a ray and checking for collision. the command canvas find could be used to return a list of possible line segments that would be intersected with our proposed path.
However to do the actual intersection test required iterating through each line found and doing the required number of tests for collision. One advantage of not using rectangles was that a smaller number of objects need to be tested as only those objects within the bounding box of the ray need to be tested. A polygon object could occupy three quarters of the problem space and thus would have to be tested with virtually all path segments.
Driving the car is straight forward. One has a limited number of options and the functions are mostly linear functions.
We turn the car and accelerate to the next point in the path. Once we hit the point we slow down. We constantly turn to drive toward the next mark. If we overshoot the mark we change to the next point in the path and try to head for this new point. If we are more than 10% different in direction that we are heading with respect with the direction we should be going then we stop accelerating and just turn.
What is missing is feedback. Once the directions have been found , the simulation data should be used as feedback to modify the placement of the path within the boundary of acceptable area.
If for example on driving the route, a wall is hit, it the required modification to the route could then be computed to prevent this from happening. Ie Either slow down eairlier of move a prior path segment further from the obstical that was hit.
One could then use graph searching to compute the list of possiblities and each of these tried in turn to see which one is quicker (not necessarily the shortest path).
This is a simple algorithm but requires that the point in the path be placed appropriately.
An alternative approach is to only accelerate for half ( actually 60% ) the length of line and then brake for the rest so that we gaurantee that we hit the next point. This however would not be a very fast way to travel the route.
During development there were some areas that caused problems. These are explained here.
The canvas performacnce drops exponentially when there are lots of objects with the same tag occuping spatially different locations. While the use of tags was not absolutely necesssary , it was the obvious way of coding the data.
There is a practical limit of approximately 10000 canvas items.
The number of points in a line also affected performance. I originally drew a trail of the cars position using 10 pixel resolution. Once the trail got to over 1000 coordinates the time to draw an extra coordinate became increasingly longer.
There are well known solutions to this type of problem. Graph searches are one of the most common. Tcl only supports linked and nested structures by use of associated arrays. The lookup time for these sparse arrays is too long to be practical for use in this problem.
The exercise was to test TCL in a real world application. The contest example was infact more a test of high order mathmatics rather than a coding challenge.
If one has an advanced understanding of Newtonian Physics and Mathmatics, then the solution would have been easy. It was infact a mathmatics exercise rather than a programming one.
The following observations were made about the abilites of TCL for this challenge:
I still use TCL in real world applications, including GPS navigation systems.
However as a complete solution I found in this case (as I often do) that 80% of the problem can be implemented very quickly. Unfortunately the remaining 20% sometimes is unachievable and one has to resort to another language to complete the task.
While it may have never been intended that TCL was a solution in it's own right, it has the flexibility to do most jobs asked of it so there becomes the expectation that it should do it all.
Most programmers are not used to using multiple languages (or paradigms) in solving a specific problem, so when faced with the prospect of having to switch to another language, they will favour developing the whole application in the alternate language.
Even using well known algorithms for solving this problem, TCL lacks the speed and depth of data structures to practicaly solve this problem completely. I give Tcl a rating of 7/10 for suitablity to this problem. I give myself 6 / 10 for the suitability of the code used in the algorithms used to solve the problem.
| Copyright © Q Solutions 2003 | Contact |