Programming Forums > Application Development > C++

keweedsmo · Feb 10th, 2006, 10:20 AM

ok I have a grid of boxes, kind of like a chess board, and I want to be able to determine the possible moves based on a unit's "move" stat. Usually move (x) will be like 1-5. When the unit is selected to move the grid must do a check to determine the possible moves on the unit. A unit with 1 move will only be able to move up,down,left,right one space, but a unit with more than 1 forms a sort of diamond shape movement. SEE ATTACHMENT FOR A GOOD VISUAL OF WHAT I AM LOOKING FOR
I am terrible at recursion and I was wondering if someone could help me out a bit. Thanx a lot.

Arevos · Feb 10th, 2006, 11:04 AM

If you're terrible at recursion, I advise getting in some practise. For instance, say you had some homework that required you to find the area of possible moves for a square on a grid, given that the square can move horizontally or vertically only one space per turn. By doing such a piece homework, you'd learn about recursion.

I'd highly recommend using this opportunity to learn, rather than trying to get other people to do the work for you.

keweedsmo · Feb 10th, 2006, 12:05 PM

sorry but this isn't for school, this is for a turn based strategy game that i'm making. I already "learned" recursion last year....but I didn't retain it. If you look at my post history i've asked a few questions about my GAME, not my HOMEWORK. :banana:

An example of how this could be done would teach me a lot. that + tutorials and i'll know what i'm doing.

Arevos · Feb 10th, 2006, 1:18 PM

Hmmmm... The images and question look rather like schoolwork, but I apologise if an error has been made.

I'll give you the benefit of the doubt, then, and give you a bit of advice upon how to approach the problem in question.

Let's first assume that our unit has it's coordinates held in an object called position. Let's further assume that position.up() returns the coordinates of the square directly above the unit, position.down() returns the square directly below, and so forth.

With any recursive problem, you have to first find a starting place. Your function is move(x), so you need to work out which value of x you'll start from. In this case, a value of 1 seems the most appropriate choice. The best method of storing all the possible moves is in a set, as each coordinate needs to be unique (ie. you wouldn't want to return an array with five (1, 1)s):

(Toggle Plain Text)

def move(position, x):
    if x == 1:
        return set(position.up(), position.down(),
                position.left(), position.right())
    else:
        # code goes here

You'll notice that the function consists of two parts. The first block (if x == 1), denotes the limiting factor; you can't get any simpler than a single move. The second, unwritten block (else), is where the recursion takes place.

For the recursion to end, we need to approach the limiting factor. In other words, x has to get smaller and smaller until it gets to one, otherwise the function will never end.

We also want to test each direction; up, down, left and right. This suggests a for-loop. So a for loop, and a decreasing value of x:

(Toggle Plain Text)

def move(position, x):
    if x == 1:
        return set(position.up(), position.down(),
                position.left(), position.right())
    else:
        possible_moves = set()
        for direction in (up, down, left, right):
            possible_moves.add( position.direction() )
            possible_moves.union( move(position.direction(), x - 1) )

        return possible_moves

This is python-like pseudocode, but I hope you get the idea of what's happening. I leave it up to an exercise for the reader to convert this into actual code, and to make it more efficient (think caching function output).

Note that a union of two sets returns a set that contains all the elements in both the original sets.

keweedsmo · Feb 10th, 2006, 1:41 PM

thanx a lot. i really appreciate it. and yea, it does look like a question for school. i remember we did freeblocks for minesweeper when I had to do a recursion project, but it was a while ago.

DaWei · Feb 10th, 2006, 1:59 PM

Another form of practice would be to form an outline with squares (or pixels) and recursively fill in the interior.

MBirchmeier · Feb 10th, 2006, 2:44 PM

Just a point of order for this 'recursion'

It would be a much more scalable algorighm if this behaivor was determined programatically as opposed to recursively.

for N's of 1 or 2 it's not a big deal, but the timing of this algorighm is 0(c^n)

An algorithm that calculates a square around the 'piece' and calculates the possible moves would be 0(n^2) making it more efficient for any N of about 4* or larger.

-MBirchmeier
<edit>* simply an estimate, it depends on individual implementations</edit>

Arevos · Feb 10th, 2006, 4:01 PM

Your method doesn't always work, MBirchmeier. Any non-trivial pattern of "blocking" squares would generate incorrect results. Of course, it may be that the AI doesn't need to be particularly clever, so your method might suffice.

However, a recursive brute-force approach isn't as inefficient as you might thing, as long as you don't repeat yourself. If you keep a cache of which squares have already been considered, and how many moves were left when the square was considered, then you can significantly reduce the number of steps required.

Instead of being O(x^n) it becomes closer to O(n^2). There's going to be an added lookup cache lookup time, of course. And it some squares may be iterated over more than once if the number of steps to get to those squares can be reduced. But if the order the squares are chosen in is picked wisely, you could reduce this algorithm to an efficiency not considerably greater than your method.

keweedsmo · Feb 13th, 2006, 10:43 AM

this might sound kinda dumb, but how would u go about returning coordinates? since its two values. Do I make a coordinate class and work with that?

InfoGeek · Feb 13th, 2006, 10:51 AM

If you want to return more than 1 value from a function, then you can either use pointers(or references) or you can bundle all the values in a struct and return that. Examples:

1) Returning mutliple values through pointers:

(Toggle Plain Text)

void foo(int *x,int *y)
{
   *x=10;
   *y=20;
}

foo(&x,&y);//call foo with addresses.

2) Returning multiple values using references

(Toggle Plain Text)

void foo(int &x,int &y)
{
    x=10;
    y=20;
}

foo(x,y);//call similar to call by value.

3) Returning multiple values using structs

(Toggle Plain Text)

struct point
{
   int x;
   int y;
}

point foo()
{
   point p;
   p.x=10;
   p.y=20;
   return p;
}

point p;
p=foo();

Hope that helps.

Feb 10th, 2006, 1:18 PM	#4
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	Hmmmm... The images and question look rather like schoolwork, but I apologise if an error has been made. I'll give you the benefit of the doubt, then, and give you a bit of advice upon how to approach the problem in question. Let's first assume that our unit has it's coordinates held in an object called position. Let's further assume that position.up() returns the coordinates of the square directly above the unit, position.down() returns the square directly below, and so forth. With any recursive problem, you have to first find a starting place. Your function is move(x), so you need to work out which value of x you'll start from. In this case, a value of 1 seems the most appropriate choice. The best method of storing all the possible moves is in a set, as each coordinate needs to be unique (ie. you wouldn't want to return an array with five (1, 1)s): (Toggle Plain Text) def move(position, x): if x == 1: return set(position.up(), position.down(), position.left(), position.right()) else: # code goes here def move(position, x): if x == 1: return set(position.up(), position.down(), position.left(), position.right()) else: # code goes here You'll notice that the function consists of two parts. The first block (if x == 1), denotes the limiting factor; you can't get any simpler than a single move. The second, unwritten block (else), is where the recursion takes place. For the recursion to end, we need to approach the limiting factor. In other words, x has to get smaller and smaller until it gets to one, otherwise the function will never end. We also want to test each direction; up, down, left and right. This suggests a for-loop. So a for loop, and a decreasing value of x: (Toggle Plain Text) def move(position, x): if x == 1: return set(position.up(), position.down(), position.left(), position.right()) else: possible_moves = set() for direction in (up, down, left, right): possible_moves.add( position.direction() ) possible_moves.union( move(position.direction(), x - 1) ) return possible_moves def move(position, x): if x == 1: return set(position.up(), position.down(), position.left(), position.right()) else: possible_moves = set() for direction in (up, down, left, right): possible_moves.add( position.direction() ) possible_moves.union( move(position.direction(), x - 1) ) return possible_moves This is python-like pseudocode, but I hope you get the idea of what's happening. I leave it up to an exercise for the reader to convert this into actual code, and to make it more efficient (think caching function output). Note that a union of two sets returns a set that contains all the elements in both the original sets.

Feb 10th, 2006, 1:59 PM	#6
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Another form of practice would be to form an outline with squares (or pixels) and recursively fill in the interior. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Feb 13th, 2006, 10:51 AM	#10
InfoGeek Professional Programmer Join Date: Jun 2005 Location: India, The great. Posts: 435 Rep Power: 4	If you want to return more than 1 value from a function, then you can either use pointers(or references) or you can bundle all the values in a struct and return that. Examples: 1) Returning mutliple values through pointers: (Toggle Plain Text) void foo(int x,int y) { x=10; y=20; } foo(&x,&y);//call foo with addresses. void foo(int x,int y) { x=10; y=20; } foo(&x,&y);//call foo with addresses. 2) Returning multiple values using references (Toggle Plain Text) void foo(int &x,int &y) { x=10; y=20; } foo(x,y);//call similar to call by value. void foo(int &x,int &y) { x=10; y=20; } foo(x,y);//call similar to call by value. 3) Returning multiple values using structs (Toggle Plain Text) struct point { int x; int y; } point foo() { point p; p.x=10; p.y=20; return p; } point p; p=foo(); struct point { int x; int y; } point foo() { point p; p.x=10; p.y=20; return p; } point p; p=foo(); Hope that helps. __________________ PFO - My daily dose of technology.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Feb 10th, 2006, 11:04 AM	#2
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	If you're terrible at recursion, I advise getting in some practise. For instance, say you had some homework that required you to find the area of possible moves for a square on a grid, given that the square can move horizontally or vertically only one space per turn. By doing such a piece homework, you'd learn about recursion. I'd highly recommend using this opportunity to learn, rather than trying to get other people to do the work for you.

Feb 10th, 2006, 12:05 PM	#3
keweedsmo Newbie Join Date: Feb 2006 Location: Albany, NY (UALBANY) Posts: 20 Rep Power: 0	sorry but this isn't for school, this is for a turn based strategy game that i'm making. I already "learned" recursion last year....but I didn't retain it. If you look at my post history i've asked a few questions about my GAME, not my HOMEWORK. :banana: An example of how this could be done would teach me a lot. that + tutorials and i'll know what i'm doing.

Feb 10th, 2006, 1:41 PM	#5
keweedsmo Newbie Join Date: Feb 2006 Location: Albany, NY (UALBANY) Posts: 20 Rep Power: 0	thanx a lot. i really appreciate it. and yea, it does look like a question for school. i remember we did freeblocks for minesweeper when I had to do a recursion project, but it was a while ago.

Feb 10th, 2006, 2:44 PM	#7
MBirchmeier Hobbyist Programmer Join Date: Oct 2005 Posts: 211 Rep Power: 3	Just a point of order for this 'recursion' It would be a much more scalable algorighm if this behaivor was determined programatically as opposed to recursively. for N's of 1 or 2 it's not a big deal, but the timing of this algorighm is 0(c^n) An algorithm that calculates a square around the 'piece' and calculates the possible moves would be 0(n^2) making it more efficient for any N of about 4* or larger. -MBirchmeier <edit>* simply an estimate, it depends on individual implementations</edit>

Feb 10th, 2006, 4:01 PM	#8
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	Your method doesn't always work, MBirchmeier. Any non-trivial pattern of "blocking" squares would generate incorrect results. Of course, it may be that the AI doesn't need to be particularly clever, so your method might suffice. However, a recursive brute-force approach isn't as inefficient as you might thing, as long as you don't repeat yourself. If you keep a cache of which squares have already been considered, and how many moves were left when the square was considered, then you can significantly reduce the number of steps required. Instead of being O(x^n) it becomes closer to O(n^2). There's going to be an added lookup cache lookup time, of course. And it some squares may be iterated over more than once if the number of steps to get to those squares can be reduced. But if the order the squares are chosen in is picked wisely, you could reduce this algorithm to an efficiency not considerably greater than your method.

Feb 13th, 2006, 10:43 AM	#9
keweedsmo Newbie Join Date: Feb 2006 Location: Albany, NY (UALBANY) Posts: 20 Rep Power: 0	this might sound kinda dumb, but how would u go about returning coordinates? since its two values. Do I make a coordinate class and work with that?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Recursion Question for a "gameboard"