2d-board algorithm: Total number of different moves to reach a location

[macdonald12]

Hello all,

I'm trying to make a program in C, but it's actually the algorithm that's giving me hell.

The goal is to create a program that calculates and displays the total number of end-locations (all locations, including similar ones) an object can reach in a 2d board (grid), using a defined maximum of moves, using only pre-defined movements.

For example, if the object would start at (0,0), and the movements would be defined as:

movement1: (x+3) (y+1)
movement 2: (x+2) (y+3)

and the maximum of allowed moves would be 8. Then what would all the possible end-location coordinates be? (of the in total (2*2*2*2*2*2 = 64 moves?).

It's probably very easy, but i've been going crazy over it for a couple of hours now - and i keep on ending up with nested for-loops that just don't work out.

If anyone out here could give me a push into the right direction, it would be very much appreciated! :)

[SVR]

If speed is not critical use a recursive function.

GenNextMove(int depth)
{
   if(depth == nMaxMove)
   {
      nTotalPos++;
      return;
   }
   for(i = 0;i<nMoves;i++)
   {
        GenNextMove(depth+1);
   }
   
}

main(...)
{
    GenNextMove(0);
}

You can pass the current position as well to store in a final positions array when MaxMoves is reached.

[macdonald12]

Thank you very much for your input SVR, i've used it to create the following code for me to practice and understand:

#include <stdio.h>
#include <stdlib.h>

int x, y = 0;

int endLocations = 0;
int maxJumps = 8;

void nextJump(int depth) {

	if(depth == maxJumps) {
		printf("Endposition (x,y) = (%d,%d)\n", x, y);
		endLocations++;
		return;
	}
	
	int i;
	
	for(i=1;i<3; i++) {
	
		switch(i) {
		
			case 1:
					x = x+3;
					y = y+1;
			case 2:
					x = x+2;
					y = y+3;
		}
		nextJump(depth+1);
	}
}

int main (int argc, char *argv[]) {

	nextJump(1);
	printf("Total endlocations: %d\n", endLocations);
	
	return 0;
}

Considering it's getting late and i probably need some sleep, i'm most likely doing something stupid now - as this keeps on returning 128 endlocations which don't look correct.

Any further help would be much appreciated, thanks alot for your input already :)

[SVR]

You'll want to keep your x & y local so each move is incremented from the correct position (you'll need to pass these in as params with the starting position sent in the first call). As it is the global position is getting added to (which is the last end position you happen to be on). The local version gets restored as you return to the previous depth and things can continue from there.

As for the depth, you are starting at 1. You should start at 0. 0 position being the start and not a move).
For each path down to MaxMove you will get positions as such ...

0: x = ?, y = ? // start pos
1: x = ?, y = ? // after move 1
2: ...
...
maxJumps: x = endx, y = endy // after maxJumps

Put a printf before the maxJumps check.

With 2 options and 8 depth I think it should give you 2^8 or 256 end positions.

[macdonald12]

Thanks again for your help! With it i was able to make a program that simulates the movement of an object in an infinite 2d-board. The movements of this object correspond to the movements of a knight in a chess-game.

This is the code for the program:

#include <stdio.h>
#include <stdlib.h>

int endLocations = 0;
int routes = 0;

int xNew, yNew;


void nextJump(int depth, int x, int y, int xEnd, int yEnd, int totalMovesAllowed) {

	int xValue = x;
	int yValue = y;

	if(depth == totalMovesAllowed) {
		if(xValue == xEnd && yValue == yEnd)
			routes++;
		endLocations++;
		return;
	}
	
	int i;
	
	for(i=1;i<9; i++) {
	
		/** Represents all eight movements a Knight can make **/
		switch(i) {
		
			case 1:
					xNew = xValue+2;
					yNew = yValue+1;
					break;
			case 2:
					xNew = xValue+2;
					yNew = yValue-1;
					break;
			case 3:
					xNew = xValue-2;
					yNew = yValue+1;
					break;
			case 4:
					xNew = xValue-2;
					yNew = yValue-1;
					break;
			case 5:
					xNew = xValue+1;
					yNew = yValue+2;
					break;
			case 6:
					xNew = xValue+1;
					yNew = yValue-2;
					break;
			case 7:
					xNew = xValue-1;
					yNew = yValue+2;
					break;
			case 8:
					xNew = xValue-1;
					yNew = yValue-2;
					break;
		}
		nextJump(depth+1, xNew, yNew, xEnd, yEnd, totalMovesAllowed);
	}
}

int main (int argc, char *argv[]) {

	int xBegin, yBegin, xEnd, yEnd, totalMovesAllowed;

	printf("Check total amount of Knightjump routes\n");
	printf("Coordinates begin position: x y: ");
	scanf("%d %d", &xBegin, &yBegin);
	printf("Coordinates end position: x y : ");
	scanf("%d %d", &xEnd, &yEnd);
	printf("Number of allowed jumps: ");
	scanf("%d", &totalMovesAllowed);

	/** Check 1 for increased efficiency 
	this is a simple check, checking for the minimum distance that needs to be covered to even reach the end-spot
	**/

	int deltaX, deltaY, movesNeededX, movesNeededY, totalMovesNeeded;
	deltaX = xEnd-xBegin;
	deltaY = yEnd-yBegin;

	if(deltaX<0)
		deltaX = deltaX*-1;
	if(deltaY<0)
		deltaY = deltaY*-1;

	movesNeededX=deltaX/2;
	movesNeededY=deltaY/2;

	if(movesNeededX<1)
		movesNeededX=1;
	if(movesNeededY<1)
		movesNeededY=1;

	if(movesNeededX >= movesNeededY)
		totalMovesNeeded = movesNeededX+1;
	else
		totalMovesNeeded = movesNeededY+1;

	if(totalMovesAllowed >= totalMovesNeeded)
	{

		/** Check 2 for increased efficiency
		This check checks for the fact that a knight-move, on a black/white-square colored board
			will always move from black -> white or vice-versa.**/

		int beginSquare, endSquare;

		if((xBegin+yBegin)%2 != 0)
			beginSquare = 0;
		else
			beginSquare = 1;
		if((xEnd+yEnd)%2 != 0)
			endSquare = 0;
		else
			endSquare = 1;

		int difference = totalMovesAllowed%2;

		if(beginSquare == endSquare && difference == 0) {
			/** Checks passed - Call actual function **/
			nextJump(0,xBegin,yBegin, xEnd, yEnd, totalMovesAllowed);
		} else if(beginSquare == endSquare && difference != 0) {
			/* not possible -> do nothing */
		} else if(beginSquare != endSquare && difference == 0) {
			/*not possible -> do nothing */
		} else if(beginSquare != endSquare && difference != 0) {
			/** Checks passed - Call actual function **/
			nextJump(0,xBegin,yBegin, xEnd, yEnd, totalMovesAllowed);
		}
	}
	printf("\nTotal amount of routes: %d\n", routes);
	
	return 0;
}

Resulting in the following output with the given input:
[IMG]http://i38.tinypic.com/10d9mx0.png[/IMG]

However, i'm supposed to be making this program more efficient - so it can calculate upfront if a given end-position can be reached from the begin-position in the given amount of moves, so that it doesn't need to calculate all routes just to come to that conclusion.

For this i added 2 checks, i think the 2nd check is fairly simple and implemented correct, however, i'm not so sure on the first check.

If anyone can give some input regarding this it would be much appreciated. And thanks again, SVR! :)

[SVR]

i'm supposed to be making this program more efficient - so it can calculate upfront if a given end-position can be reached from the begin-position in the given amount of moves, so that it doesn't need to calculate all routes just to come to that conclusion.

That is a typical search problem. The given solution is a 'depth first' search where you search down the chain of moves before considering other moves. Potentially more efficient is a 'breadth first' search where you look at all moves at a given depth before proceeding down the chain.
Each has it's merit for a given task.

Most chess programs use a combination algorithm. Do a web search for 'A* search' and 'iterative deepening'.

Some of the logic can get pretty hairy so enjoy :)

As far as the current code, you should check the xEnd & yEnd before the depth. Otherwise you're only going to get routes that are maxMoves long. It may take less than that.

I dont see anything glaringly wrong with your check#1. It makes sense that the knight can move a max of 2 in any move so anything farther than movesallowed*2 can't be reached.
I bet if you think on it hard enough you can expand that logic to determine exactly how many moves it will take without having to search at all.