Results 21 to 31 of 31
Thread: Recursion.
 05092010, 01:32 PM #21Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
 05092010, 01:34 PM #22Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
it reaches the end 4 times, (put a system.out.println there).
my standard input/output spits out,
24
26
26
28
then it just hangs.
 05092010, 01:35 PM #23Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
I'm kinda stabbing in the dark here, since I don't have enough of the code to compile this, so I'm just kinda stepping through it in my head.
 05092010, 01:37 PM #24Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Want the whole thing?
Java Code:import java.awt.*; import java.awt.event.*; import java.applet.*; import javax.swing.*; import java.util.*; public class PRobTD extends JApplet implements ActionListener, Runnable, MouseListener, MouseMotionListener, KeyListener { JLabel layer1, layer2, layer3, title, menuScreen, gameScreen, lGold, lLives, towersTitle, lWave; JButton startGame, quitGame, tower1, tower2, tower3, startWave; JRadioButton easy, medium, hard; int gold, lives, wave; TDSquare[] [] squares = new TDSquare [12] [14]; public void init () { setSize (600, 500); getContentPane ().setLayout (null); menuScreen = new JLabel (); menuScreen.setBounds (0, 0, getWidth (), getHeight ()); menuScreen.setBackground (Color.red); menuScreen.setOpaque (true); gameScreen = new JLabel (); gameScreen.setBounds (0, 0, getWidth (), getHeight ()); gameScreen.setBackground (Color.white); gameScreen.setOpaque (true); title = new JLabel ("PRob's Tower Defense"); title.setBounds (0, 35, getWidth (), 50); title.setHorizontalAlignment ((int) CENTER_ALIGNMENT); title.setFont (new Font ("Times New Roman", Font.BOLD, 40)); startGame = new JButton ("Start"); startGame.setBounds (getWidth () / 2  100, title.getY () + title.getHeight () + 50, 200, 60); startGame.setText ("Start Game"); startGame.addActionListener (this); ButtonGroup difficulty = new ButtonGroup (); easy = new JRadioButton ("Easy"); easy.setBounds (startGame.getX (), startGame.getY () + startGame.getHeight () + 10, startGame.getWidth (), 20); easy.setBackground (menuScreen.getBackground ()); easy.setSelected (true); medium = new JRadioButton ("Medium"); medium.setBounds (easy.getX (), easy.getY () + easy.getHeight (), easy.getWidth (), easy.getHeight ()); medium.setBackground (menuScreen.getBackground ()); hard = new JRadioButton ("Difficult"); hard.setBounds (medium.getX (), medium.getY () + medium.getHeight (), medium.getWidth (), medium.getHeight ()); hard.setBackground (menuScreen.getBackground ()); difficulty.add (easy); difficulty.add (medium); difficulty.add (hard); menuScreen.add (title); menuScreen.add (startGame); menuScreen.add (easy); menuScreen.add (medium); menuScreen.add (hard); layer1 = new JLabel (); layer1.setBorder (BorderFactory.createLineBorder (Color.black)); layer1.setBounds (70, 20, 360, 420); layer2 = new JLabel (); layer2.setBorder (BorderFactory.createLineBorder (Color.black)); layer2.setBounds (70, 20, 360, 420); layer3 = new JLabel (); layer3.setBorder (BorderFactory.createLineBorder (Color.black)); layer3.setBounds (70, 20, 360, 420); for (int i = 0 ; i < squares.length ; i++) { for (int j = 0 ; j < squares [i].length ; j++) { squares [i] [j] = new TDSquare (0); squares [i] [j].setBounds (i * 30, j * 30, 30, 30); squares [i] [j].setBackground (Color.red); squares [i] [j].setOpaque (true); squares [i] [j].setBorder (BorderFactory.createLineBorder (Color.black)); layer3.add (squares [i] [j]); } } lGold = new JLabel ("Gold: "); lGold.setBounds (layer1.getX () + layer1.getWidth () + 10, layer1.getY (), 150, 20); lLives = new JLabel ("Lives: "); lLives.setBounds (lGold.getX (), lGold.getY () + lGold.getHeight () + 10, 150, 20); lWave = new JLabel ("Wave: "); lWave.setBounds (lLives.getX (), lLives.getY () + lLives.getHeight () + 10, 150, 20); startWave = new JButton ("Start Wave"); startWave.setBounds (lWave.getX (), lWave.getY () + lWave.getHeight () + 10, 150, 20); towersTitle = new JLabel ("Towers"); towersTitle.setBounds (layer1.getX () + layer1.getWidth (), startWave.getY () + startWave.getHeight () + 10, getWidth ()  (layer1.getX () + layer1.getWidth ()), 30); towersTitle.setHorizontalAlignment ((int) CENTER_ALIGNMENT); tower1 = new JButton ("1"); tower1.setBounds (towersTitle.getX (), towersTitle.getY () + towersTitle.getHeight () + 10, 50, 50); tower2 = new JButton ("2"); tower2.setBounds (tower1.getX () + tower1.getWidth () + 10, tower1.getY (), 50, 50); tower3 = new JButton ("3"); tower3.setBounds (tower2.getX () + tower2.getWidth () + 10, tower2.getY (), 50, 50); quitGame = new JButton ("Quit"); quitGame.setBounds (10, getHeight ()  50, 100, 40); quitGame.addActionListener (this); gameScreen.add (layer1); gameScreen.add (layer2); gameScreen.add (layer3); gameScreen.add (quitGame); gameScreen.add (lGold); gameScreen.add (lLives); gameScreen.add (towersTitle); gameScreen.add (tower1); gameScreen.add (tower2); gameScreen.add (tower3); gameScreen.add (lWave); gameScreen.add (startWave); getContentPane ().add (menuScreen); getContentPane ().add (gameScreen); loadMenu (); ArrayList path = findShortestPath (0, 0, 11, 13, new ArrayList ()); System.out.println (path.size ()); } public void loadMenu () { gameScreen.setVisible (false); menuScreen.setVisible (true); } public void loadGame (int difficulty) { menuScreen.setVisible (false); gameScreen.setVisible (true); getContentPane ().setBackground (Color.white); switch (difficulty) { case 0: gold = 2000; lives = 40; break; case 1: gold = 1500; lives = 20; break; case 2: gold = 1000; lives = 10; break; } lGold.setText ("Gold: " + gold); lLives.setText ("Lives: " + lives); } public void actionPerformed (ActionEvent e) { if (e.getSource () == startGame) { if (easy.isSelected ()) loadGame (0); else if (medium.isSelected ()) loadGame (1); else loadGame (2); } else if (e.getSource () == quitGame) { loadMenu (); } } public boolean isTouching (int x1, int y1, int x2, int y2) { if (x1 + 1 == x2 && y1 == y2) return true; else if (x1  1 == x2 && y1 == y2) return true; else if (x1 == x2 && y1 + 1 == y2) return true; else if (x1 == x2 && y1  1 == y2) return true; return false; } public ArrayList findShortestPath (int fromx, int fromy, int tox, int toy, ArrayList path) { ArrayList temp = (ArrayList) path.clone (); ArrayList[] temps = new ArrayList [4]; temp.add (squares [fromx] [fromy]); if (isTouching (fromx, fromy, tox, toy)) { System.out.println (temp.size ()); return temp; } else { int[] paths = new int [4]; if (fromx < 11 && !squares [fromx + 1] [fromy].block && !temp.contains (squares [fromx + 1] [fromy])) temps [0] = findShortestPath (fromx + 1, fromy, tox, toy, temp); else temps [0] = null; if (fromy < 13 && !squares [fromx] [fromy + 1].block && !temp.contains (squares [fromx] [fromy + 1])) temps [2] = findShortestPath (fromx, fromy + 1, tox, toy, temp); else temps [2] = null; if (fromx > 0 && !squares [fromx  1] [fromy].block && !temp.contains (squares [fromx  1] [fromy])) temps [1] = findShortestPath (fromx  1, fromy, tox, toy, temp); else temps [1] = null; if (fromy > 0 && !squares [fromx] [fromy  1].block && !temp.contains (squares [fromx] [fromy  1])) temps [3] = findShortestPath (fromx, fromy  1, tox, toy, temp); else temps [3] = null; for (int i = 0 ; i < 4 ; i++) if (temps [i] != null) paths [i] = temps [i].size (); else paths [i] = 10000; return temps [smallest (paths)]; } } public int smallest (int[] nums) { int smallest = nums [0]; int smallestIndex = 0; for (int i = 1 ; i < nums.length ; i++) { if (nums [i] < smallest) { smallest = nums [i]; smallestIndex = i; } } return smallestIndex; } public void mousePressed (MouseEvent e) { } //UNUSED METHODS public void run () { } public void mouseClicked (MouseEvent e) { } public void mouseReleased (MouseEvent e) { } public void mouseEntered (MouseEvent e) { } public void mouseExited (MouseEvent e) { } public void mouseMoved (MouseEvent e) { } public void mouseDragged (MouseEvent e) { } public void keyTyped (KeyEvent e) { } public void keyPressed (KeyEvent e) { } public void keyReleased (KeyEvent e) { } //END OF USELESS METHODS } class TDSquare extends JLabel { int squareType; boolean block = false; public TDSquare (int squareType) { } } class Enemy extends JLabel { int hp; int speed; public Enemy (int hp, int speed) { this.hp = hp; this.speed = speed; } }
 05092010, 02:37 PM #25Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
I hate to leave you hanging, but I'm stumped.
At least you know that at some point it did find the shortest path, you just gotta figure out why it doesn't stop calling itself.
 05092010, 04:14 PM #26Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Okay thanks anyway,
good to know i'm closer to the right direction anyway,
Still +repped you
 05092010, 05:21 PM #27Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
damn, the number that it gives is actually the first path it finds, not the shortest. i got it to not call any more methods once it found the path, but it's not the shortest one, precedence is given to right and down.
 05092010, 08:27 PM #28
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,390
 Blog Entries
 7
 Rep Power
 25
Using recursion for path finding is fine but it is just a blind search; i.e. your method keeps on going until it finds an arbitrary path. There is no guarantee that the found path is the shortest possible. Therefore you have to keep track of a shortest path found so far. If the new found path happens to be shorter than a previously found path, remember the new path and forget about the other one. Your recursive method should continue finding other paths and repeat the check. There is a 'branch and cut' methodology that is capable of cutting off a search when it can't find a better solution but don't think of it now.
kind regards,
Jos
 05092010, 11:07 PM #29Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Yes this is the way it was initially written, and the most recent code example should have it this way, it keeps the shortest path, however if it keeps calling methods it never returns to the main call, that's why i had to make it cut off once it finds a path, only to realise that it's not necessarily the shortest path.
can you read it and offer suggestions?
here's the code without explicitly breaking out:
Java Code:public ArrayList findShortestPath (int fromx, int fromy, int tox, int toy, ArrayList path) { ArrayList temp = (ArrayList) path.clone (); ArrayList[] temps = new ArrayList [4]; temp.add (squares [fromx] [fromy]); if (isTouching (fromx, fromy, tox, toy)) { System.out.println (temp.size ()); return temp; } else { int[] paths = new int [4]; if (fromx < 11 && !squares [fromx + 1] [fromy].block && !temp.contains (squares [fromx + 1] [fromy])) temps [0] = findShortestPath (fromx + 1, fromy, tox, toy, temp); else temps [0] = null; if (fromy < 13 && !squares [fromx] [fromy + 1].block && !temp.contains (squares [fromx] [fromy + 1])) temps [2] = findShortestPath (fromx, fromy + 1, tox, toy, temp); else temps [2] = null; if (fromx > 0 && !squares [fromx  1] [fromy].block && !temp.contains (squares [fromx  1] [fromy])) temps [1] = findShortestPath (fromx  1, fromy, tox, toy, temp); else temps [1] = null; if (fromy > 0 && !squares [fromx] [fromy  1].block && !temp.contains (squares [fromx] [fromy  1])) temps [3] = findShortestPath (fromx, fromy  1, tox, toy, temp); else temps [3] = null; for (int i = 0 ; i < 4 ; i++) if (temps [i] != null) paths [i] = temps [i].size (); else paths [i] = 10000; return temps [smallest (paths)]; } }
this will always println 4 times, and then hang.
the 4 numbers that printout are
x
x+2
x+2
x+4
where x is the length of the first found path
 05102010, 04:28 AM #30Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Okay update:
Java Code:public void findShortestPath (int fromx, int fromy, int tox, int toy, ArrayList path) { if (path.size () + 2 > tempShort) { return; } ArrayList temp = (ArrayList) path.clone (); temp.add (squares [fromx] [fromy]); if (isTouching (fromx, fromy, tox, toy)) { shortestPath = temp; tempShort = shortestPath.size (); System.out.println (tempShort); return; } else { if (fromx < 11 && !squares [fromx + 1] [fromy].block && !temp.contains (squares [fromx + 1] [fromy])) findShortestPath (fromx + 1, fromy, tox, toy, temp); if (fromy < 13 && !squares [fromx] [fromy + 1].block && !temp.contains (squares [fromx] [fromy + 1])) findShortestPath (fromx, fromy + 1, tox, toy, temp); if (fromx > 0 && !squares [fromx  1] [fromy].block && !temp.contains (squares [fromx  1] [fromy])) findShortestPath (fromx  1, fromy, tox, toy, temp); if (fromy > 0 && !squares [fromx] [fromy  1].block && !temp.contains (squares [fromx] [fromy  1])) findShortestPath (fromx, fromy  1, tox, toy, temp); } }
i made the method void to avoid worrying about what to do with the throw away returns.
instead it saves the shortest path that it has found to a classlevel field, and at the top of the method if there is no chance of the current (iteration?) of the method being the shortest, then it just returns back.
you should be glad to hear that this method works, yes it finds the shortest path! clap!!!
new problem, it finds it quickly if it's close to the end with little obstacles, but from the beginning it takes too long.
the blue squares are the obstacles i made, and the orange path is the path that my method found. this is correct, however it took the method over 1 minute to finish, and considering that the path could be frequently changing throughout the game, this is unacceptable.
Anyone got any ideas?
 05102010, 01:06 PM #31Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Java Code:public int shortestPossible (int fromx, int fromy, int tox, int toy) { return Math.abs (toy  fromy) + Math.abs (tox  fromx); } public void findShortestPath (int fromx, int fromy, int tox, int toy, ArrayList path) { if (path.size () + 2 > tempShort) { return; } ArrayList temp = (ArrayList) path.clone (); temp.add (squares [fromx] [fromy]); if (isTouching (fromx, fromy, tox, toy)) { shortestPath = temp; tempShort = shortestPath.size (); System.out.println (tempShort); return; } else { if (fromx < 11 && !squares [fromx + 1] [fromy].block && !temp.contains (squares [fromx + 1] [fromy]) && path.size () + shortestPossible (fromx + 1, fromy, 11, 13) + 1 < tempShort) findShortestPath (fromx + 1, fromy, tox, toy, temp); if (fromy < 13 && !squares [fromx] [fromy + 1].block && !temp.contains (squares [fromx] [fromy + 1]) && path.size () + shortestPossible (fromx, fromy + 1, 11, 13) + 1 < tempShort) findShortestPath (fromx, fromy + 1, tox, toy, temp); if (fromx > 0 && !squares [fromx  1] [fromy].block && !temp.contains (squares [fromx  1] [fromy]) && path.size () + shortestPossible (fromx  1, fromy, 11, 13) + 1 < tempShort) findShortestPath (fromx  1, fromy, tox, toy, temp); if (fromy > 0 && !squares [fromx] [fromy  1].block && !temp.contains (squares [fromx] [fromy  1]) && path.size () + shortestPossible (fromx, fromy  1, 11, 13) + 1 < tempShort) findShortestPath (fromx, fromy  1, tox, toy, temp); } }
Thanks anyway to anyone that tried to help.
Similar Threads

recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
Recursion
By kathyla18 in forum New To JavaReplies: 2Last Post: 04092009, 02:26 AM 
Recursion
By Mika in forum New To JavaReplies: 5Last Post: 01042009, 02:13 AM 
Recursion help
By rjg_2186 in forum New To JavaReplies: 1Last Post: 01022009, 09:03 AM 
Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 01:51 PM
Bookmarks