[m-dev.] ICFP Contest: Any signs of life?

[Ralph Becket]

Hi Chaps,

I'm working on a version at home, too.

Some of my thoughts...

The search space is so massive that direct branching search seems the
wrong way to go about solving the problem, mainly because turning and
acceleration are both *very* slow (it takes 500 ticks just to turn 90
degrees.)

A better starting point, I believe, is as follows:
(1) plan to follow the current direction of the car as far as possible
while reducing the distance to the finishing line (this means
accelerating for 2/3 of the journey and braking to a halt for the last
1/3);
(2) at the destination, find a straight line course that will lead to
the maximum reduction in distance to the finishing line & go to step
(1).

This gives us an easy-to-implement solution that won't do too badly.
Next, we can try optimizing the path.  For example:

	A --------------- B
			  |
			  |
			  |
			  |
			  |
			   
			  C

might be optimizable to

	A ------------    B
		      \	   
		       \   
			\  
			 \ 
			  |
			   
			  C

or even better, to a curved path (probably best to just consider just
straightforward constant turning paths or constant turning modulo
acceleration.)

What do you reckon?

-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------