Page 2 of 2 FirstFirst 12
Results 21 to 31 of 31

Thread: Recursion.

  1. #21
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Okay thanks for that, forgot about clone, (still had to cast into type ArrayList).

    but, now the method never returns to the final call, but it doesn't stackoverflow either.

    God i hate recursion...

  2. #22
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    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.

  3. #23
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    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.

  4. #24
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    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;
        }
    }
    Sorry for lack of comments, there's a lot of unimplemented, unfinished stuff in there that you kind of need to ignore.

  5. #25
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    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.

  6. #26
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Okay thanks anyway,

    good to know i'm closer to the right direction anyway,

    Still +repped you

  7. #27
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    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.

  8. #28
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,778
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Cruncher View Post
    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.
    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

  9. #29
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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

    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

  10. #30
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    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);
            }
        }
    Okayyy

    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 class-level 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?

  11. #31
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    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);
            }
        }
    nevermind, i finished it, i just checked if the square i'm about to check would be close enough to the end even if there were no obstacles, this weeds out a lot of method iterations.

    Thanks anyway to anyone that tried to help.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  2. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 03:26 AM
  3. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 02:13 AM
  4. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 09:03 AM
  5. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 01:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •