Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

# moving through 2D arrays

Deyna Cegielski
Ranch Hand

Joined: Nov 24, 2004
Posts: 60
i have a 2d array (a maze) which is filled with true and false (true = free space, false = wall).

using a stack im trying to write a method to find the correct path through the maze by first going right (if i can), then down(if i can), then left...and then up.

each free point i goto gets set as visited and if i come to a dead end (cant go right down left or up) this point is set as "discard" and i move back a step (using the stack) and check to see if going right down left or up is a free space, not doing anything if it is a wall or it has been discarded. i can do this with recursion but without im having difficulties, i can visualise what to do its writing the code im having troubles with.
Norm Miller
Ranch Hand

Joined: May 21, 2002
Posts: 56
This is a problem which really solves best with a recursive solution. If you already have that, why change it? If you must change it, you can make a recursive solution into an iterative one. I googled for a couple minutes using the keywords "recursion" and "iteration" and found several sites showing how it is done.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24149

27

Originally posted by Deyna Cegielski:
i can visualise what to do its writing the code im having troubles with.

OK, describe what you want to do, and we'll give you some pointers.

Deyna Cegielski
Ranch Hand

Joined: Nov 24, 2004
Posts: 60
sorry...

"im trying to write a method that moves through a 2d array point by point. at each point it trys to go right if it can it goes right if it cant it trys to go down, then left, then up. if it can move then it will at the process is repeated for the new point. this can be done with recursion but i have no idea how to implement this as an iterative proceess and im not allowed to use recursion. please help!"
Deyna Cegielski
Ranch Hand

Joined: Nov 24, 2004
Posts: 60
maybe its easier if i translate that into a bit of pseudocode...

1.for each point
is point up "free space", if so go there, repeat 1.
is point to right "free space", if so go there, repeat 1.
is point down "free space", if so go there, repeat 1.
is point to left "free space, if so go there, repeat 1.

the implementation at each step i can do myself, its setting up the above as an interative process i cant do. any help would be be greatly appreciated.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Also, you might need a stack to help back up when you reach a dead end.

Layne

Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
A little more detail on the idea above ... Recursion gives you a new set of local variables on the JVM's stack. To convert from recursion to iteration you can put your local variables on your own stack instead. If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

I'd make a little data-only object with all the local variables I need, maybe row, column, length of path, etc. Then any time you were thinking about calling yourself recursively, push the current object onto the stack and initialize a new one. Where the recursion returned, pop the prior object off the stack again.

I remember doing this in COBOL to evaluate an expression with nested parens. (Still have the code on this PC!) Ah, the good old days!

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Stan James:
If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

The Java API has had a Stack class since JDK 1.0, according to the javadocs.
Layne
[ November 30, 2004: Message edited by: Layne Lund ]

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.

subject: moving through 2D arrays