figuring out a maze

[GateKeeper]

I am curious if anyone has ever tried to write a script that could find the shortest way through a maze, and if so, where I might find it. I have a pretty good idea how to go about it on a basic level, but the problem that seems to arise centers around a point where a choice of directions has to be made. Logic would dictate that at such a point, I would have to begin building a tree of sorts, following each of the possible paths until they reached a point where they couldn't continue or had reached the end of the maze. Obviously this problem would continue to get worse if additional choices had to be made. If anyone has any ideas of how to go about writing such a script (if it is possible) I am all ears.

GK

[beetle]

Are you looking for javascript that does this? Where would your mazes come from? Picture files or data arrays or ????

[whammy]

I would hope data, since javascript cannot read picture formats.

:D

[GateKeeper]

The information would come from a data array that is based off of an image. A lot of this goes back to the script I was working on earlier to plot a line across a map. The idea I am shooting for is to have that line adjust itself based on terrain features. For instance, instead of going straight over the top of a mountain, it would look for lower ground. Instead of going straight through a forested area, it would go around it.

The data array I would be building would factor in such things as mountains, forests, roads, rivers and other such features that might affect the amount of time it would take someone to travel from point A to point B. The array would be like a grid representation of the map in use.

The real problem comes in when I have to consider that the data elements cant be as simple as 0 and 1. In reality, once everything is factored in, those elements could range anywhere from 0 to 10. Essentially, what I need to be able to do is compare the current position to the next possible positions and determine which would be easier to travel through while at the same time making sure that they don't lead to a dead end.

In all honesty, I am not sure if it can be done or not. To the best of my recolection, I have never seen anything save a full blown program that could do this sort of thing with any reasonable degree of success. I know a friend of mine and I tried to write this sort of thing several years ago in Pascal. We had a fair degree of success, but we were only using values of 1 and 0. Still, though, I would be interested in hearing everyone's thoughts on this. If worse comes to worse, I have a back-up plan from those guys at NASA.

GK:thumbsup:

[RadarBob]

I recall from my old C/C++ textbook there were problems in there concerning taversing mazes. C How to Program by Deitel & Deitel. These guys have written textbooks for several languages (javascript NOT being one of them), and guess what? all their examples and problems are the same. So take a look at their current stuff at your bookstore.

Anyway I recall they used two dimentional arrays and discussed brute force and random selection for "which way to go?" No fancy traversing algorithms per se. Also threw in some recursive discussion. Fun had by one and all.

[GateKeeper]

Dontcha know, I do a little web searching on mazes and find a couple two or three sites that discuss the details of solving mazes but not a one of them shows any of the algorythms used to do it. Of course they describe all of them but they dont show a single one. On a side note, however, I am beginning to get an idea of how I might go about it by using a 3D array with the uppermost layer being the actual maze and the lower layers being the possible solutions generated by the script.

I suppose if worse comes to worse, I could always plot out all the possible solutions myself and then use the mouse clicks to call a specific link with the map with the solution on it, however, that would eat up a load of web space, no?

GK:thumbsup:

[RadarBob]

Do an internet search for the keyword "topology". That branch of mathematics has some of it's roots, I believe, in the old problem of getting from A to B in the most efficient way.

[Vladdy]

I think the solution will be quite different for the case of a maze (where you have just go and no go) and the case of different terrain affecting the speed gradually (I played Asherons Call for a few months right after it came out, so I have some idea of what you are up to ;) ).

The mase problem is easier and the best solution can be found without having to iterate through all possibilities. The "terrain difficulty" problem, especially if you have certain areas that are "not passable", is much more involved. Depending on the size of your array, javascipt may not be up to par for the task. You will be able to code it, but speed wise it may take it awhile to do the calculation. You may have to use an executable on the server to perform the task.

E-mail me if you are interested in the further discussion, I have a very good idea how to solve the maze problem and can look into the "terrain difficulty" problem as well.

[GateKeeper]

Hey Vladdy, I tried to email you based on the email from your website, but the mailerdeamon returned it, need a valid email addy from ya when you have time.

GK

[Garadon]

i sounds to me what ur looking for is called pathfinding

here is a link concerning that sort of happy reading :D
http://theory.stanford.edu/~amitp/GameProgramming/

[GateKeeper]

Mucho Thanks, Garadon, I think that is exactly what I am looking for, time to go do some reading

GK:thumbsup: