rtutus
03-08-2006, 03:18 PM
For this challenge, you'll need to write an algorithm to find your way from one corner of a field to another as fast as possible. You will be given a starting point and an ending point, and you'll need to tell us how long it will take you to get from start to finish. The field is a grid, and you can only move up, down, left and right. Each move of one grid square takes 1 second.
Unfortunately, there's also walls in the way. Each wall either runs vertically or horizontally on the field. The walls are of varying height. To climb up a wall that's one meter higher than where you are now (the field is at a height of zero) will ......The rest ll be here:
http://www.scm.ca/programmingchallenge/maze.htm
Ultimater
03-09-2006, 01:35 PM
Here are some obvious things you will need to do:
Build a 2D array to map the whole field and all it's walls -- use numbers to represent the height of walls and 0s for the ground-level (if you later make the thing more complex by adding more obstacles to the map like additional players, you'd want to represent them using letters). Use a 2nd array to represent the wanted start and finish goals.
You will surely need to keep track of your cursor or "man". Best do this in a seperate array or object. In this cursor-object, you'll want to keep a 3D map of your man's coords on the map -- both x and y axis as well as how high off the ground-level he is for calculating wall climbing. When he's climbing a wall, raise his z-axis, when he finally finishes climbing a wall, move his z-axis back to 0. Onload, you'd want to have the man's coords look at the start-and-finish array in order to set itself to the start point.
As far as thinking, I think it best to first calculate how many seconds it will take to move two or three spaces from one square to another in each directon until you have a map. Use a loop to generate a huge array containing each move and the resulting time used as well as the direction you move.
e.g. [[1,1],[2,1],[1,0],1]
([1,0] is the directon)
if you'd want to move back, the array would look like this:
[[2,1],[1,1],[-1,0],1]
Then loop through all the possible moves and filter out the moves that bring you in the right direction from the ones that don't. This speeds-up thinking by removing moves like [[2,1],[1,1],[-1,0],1] from the possible moves because you will never have to use this move because even if you ever get to that square and moved from here to there, you'd be moving in the WRONG direction. So you can totally omit the move from your possible move list.
Then loop through the possible moves that point you in the right direction and compare the results to find the fastest route.
Maybe I'll have some time free later and I'll be able to write you some JavaScript.
Edit: actually moves like [[2,1],[1,1],[-1,0],1] which seemingly move you in the wrong direction MIGHT be an option in the case of avoiding very tall walls. Hmph..... Let me re-think this... If only there were a way to get rid of the third dimension from the algorithm and express the entire map using only 2 dimensions... hmmm.... How to express this map using only 1's and 0's... Need a way so the algorithm can compair the route around a wall to the time it takes to jump the wall.....
var walls=new Array(
[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [11],[0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [11],[0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [11],[0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [11],[0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [0], [0], [3], [5], [5], [5], [5], [5], [5],
[0], [0], [0], [0], [3], [0], [0], [0], [0], [0], [0],
[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0],
[10],[10],[10],[10],[10],[10],[10],[10],[10],[10],[0],
[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0],
[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0]
);