hiii

imagine your self you have a hexagon board fill up with hexagons

now, the ball can only move from one place to another if he has an "open way"

"open way" - an empty hexagon(s)

for example if the user wants to move tha ball from 0 to 32 he needs free hexagons to get there

x-10 x-9

x-1 x x+1

x+9 x+10

oh, the ball has 6 directions that it can move

note in the picture blow , the numbers on the board

is how i access to each cell

so for example cell between 4 to 9 . doesnt exist , or better they do exist but not in use at this moment

i need help . i tried to think on this several days.. but i cant find any solution to my problem .. any ideas?

thanks

eko

EDIT: upload new attachment

imagine your self you have a hexagon board fill up with hexagons

now, the ball can only move from one place to another if he has an "open way"

"open way" - an empty hexagon(s)

for example if the user wants to move tha ball from 0 to 32 he needs free hexagons to get there

x-10 x-9

x-1 x x+1

x+9 x+10

oh, the ball has 6 directions that it can move

note in the picture blow , the numbers on the board

is how i access to each cell

so for example cell between 4 to 9 . doesnt exist , or better they do exist but not in use at this moment

i need help . i tried to think on this several days.. but i cant find any solution to my problem .. any ideas?

thanks

eko

EDIT: upload new attachment

First, I can not see your image. Second, I'm not sure of the question, but if your just want to know a possible way to address the grid then I would use the method below. See the colored numbers? The hexagon grid is seen as two arrays (you can combine them in your code, but we are just brain storming here) - one yellow, one white. Knowing if there is an open space is simply a matter of checking the two arrays.

uploaded new attachment

any ideas?

thanks

eko

any ideas?

thanks

eko

You could store an array of valid ranges like this:

Just calculate the position as if you had an infinite board, then check if the result fits into one of the ranges..

Thomas

```
```

ranges db 0,4,9,14,18,24,27,34,36,44.... ; 0-4, 9-14, 18-24 etc

Just calculate the position as if you had an infinite board, then check if the result fits into one of the ranges..

Thomas

i can calculete this range ... this is not my problem

my problem . is how to get the way

the ball has 6 directions to "walk" throw

and if i need to go from 0 to 37 or thing like that .

i need to make up an algo to check if the way is free

my problem . is how to get the way

the ball has 6 directions to "walk" throw

and if i need to go from 0 to 37 or thing like that .

i need to make up an algo to check if the way is free

You mean like solving a maze puzzle?

You could make a big tree of possible moves (recursively), and find out if one of the paths reaches the destination. There are good algorithms for optimizing the tree search (http://www.generation5.org/simple_search.shtml, http://www.generation5.org/astar.shtml)

Thomas

You could make a big tree of possible moves (recursively), and find out if one of the paths reaches the destination. There are good algorithms for optimizing the tree search (http://www.generation5.org/simple_search.shtml, http://www.generation5.org/astar.shtml)

Thomas

exactly like solving a mze puzzle one the problem I need to fit it to my board and that each ball can move to 6 directions

any ideas?

any ideas?

if i do trees search . does it check the all posibilities?

eko,

Since you said you can determine the range. (I'm not sure if I understood the problem but here's my try.)

Intro:You might want to save the image below while you are reading the content of this thread.

1. Create an array of 80 bytes.

2. Initializing all 80 bytes to 0.

3. Mark the walls(not free cells) for example 10, 20 and 30 as 1

4. We all know that by going left from current position the number decreases by 1 and going right increases the current position by 1.

5. If we go NW or SE from the current position, the cell difference is 10.

E.G. 11 going to 21 the difference is |10| {|x| absolute value}

How do we determine if the ball is moving NW or SE:

NW: the starting position is greater than the ending position

SE: the starting position is less than the ending position

6. If we go NE or SW from the current position, the cell difference is 9.

E.G. 11 going to 20 the difference is 9

How do we determine if the ball is moving NE or SW:

NE: the starting position is greater than the ending position

SW: the starting position is less than the ending position

You can derived from the differences if the ball's movement is valid or not.

Look at the sample image below. We start at 21.

1. If we go left subtract 1 we get 20 then check if array 20 is equal to 1, if 1 then it's a "wall" or "not free"

2. going right adds 1 to the current position...

3. Going TO 1 FROM 21. Since the starting position is greater than the ending position we know it's going north but we don't know if its either NE or NW. (see above condition)

We can see in our eyes it's going NW but algorithmically we don't know the solution.

Solution:

first we know that going NW the difference of cells is 10 and going NE the difference of cells is 9. (see above condition)

checking if ball is going NE

If we subtract 21 by 9 we get 12

continue to subtract that by 9 we get 3 (continue this step until a match of the ending position is found or the difference is a negative value)

is 3 == 1? no, so NE isn't the direction of the ball

checking if ball is going NW

If we subtract 21 by 10 we get 11

continue to subtract that by 10 we get 1 (continue this step until a match of the ending position is found or the difference is a negative value)

is 1 == 1? yes, so NW is the direction of the ball

the value 1 we are checking is the ending position and the current difference of cells. Here we conclude that this is a valid move.

if any checking of the values doesn't match, then the move is invalid. for example going TO 10 FROM 21 there is no way on the subtraction process you'll ever get a difference of 10 on both checks(NW and NE directions)

Now checking for exceeding a "wall"...

if you take a look at the picture below, you can see we start at cell 21. for example we go to cell 18. We can see that there is a block or "wall" on 20. To check this ambiguity. All you have to do is determine the start the by adding or subtracting from the current position until you arrived at the ending position while checking if the array has a flag of 1.

E.G.

from 21 going to 18.

1. 21 - 1 == 20 check array[20] if it's set to 1 if it's not, decrease further

2. Since 20 is set to 1 then the move is invalid...

It's complicated than first thought. I hope you understood what I've said. As long as you follow the rules I set above, I'm sure you can solve the problem.

The lines below shows the possible movements.

P.S. as for determining whether going E or W, this condition happens when the check for NW and NE or SE or SW doesn't conclude any match of the ending position.

I have not tested this on a program, there might be errors on something I've said... :) forgive me if there are errors or have not understood the problem. :grin:

Since you said you can determine the range. (I'm not sure if I understood the problem but here's my try.)

Intro:You might want to save the image below while you are reading the content of this thread.

1. Create an array of 80 bytes.

2. Initializing all 80 bytes to 0.

3. Mark the walls(not free cells) for example 10, 20 and 30 as 1

4. We all know that by going left from current position the number decreases by 1 and going right increases the current position by 1.

5. If we go NW or SE from the current position, the cell difference is 10.

E.G. 11 going to 21 the difference is |10| {|x| absolute value}

How do we determine if the ball is moving NW or SE:

NW: the starting position is greater than the ending position

SE: the starting position is less than the ending position

6. If we go NE or SW from the current position, the cell difference is 9.

E.G. 11 going to 20 the difference is 9

How do we determine if the ball is moving NE or SW:

NE: the starting position is greater than the ending position

SW: the starting position is less than the ending position

You can derived from the differences if the ball's movement is valid or not.

Look at the sample image below. We start at 21.

1. If we go left subtract 1 we get 20 then check if array 20 is equal to 1, if 1 then it's a "wall" or "not free"

2. going right adds 1 to the current position...

3. Going TO 1 FROM 21. Since the starting position is greater than the ending position we know it's going north but we don't know if its either NE or NW. (see above condition)

We can see in our eyes it's going NW but algorithmically we don't know the solution.

Solution:

first we know that going NW the difference of cells is 10 and going NE the difference of cells is 9. (see above condition)

checking if ball is going NE

If we subtract 21 by 9 we get 12

continue to subtract that by 9 we get 3 (continue this step until a match of the ending position is found or the difference is a negative value)

is 3 == 1? no, so NE isn't the direction of the ball

checking if ball is going NW

If we subtract 21 by 10 we get 11

continue to subtract that by 10 we get 1 (continue this step until a match of the ending position is found or the difference is a negative value)

is 1 == 1? yes, so NW is the direction of the ball

the value 1 we are checking is the ending position and the current difference of cells. Here we conclude that this is a valid move.

if any checking of the values doesn't match, then the move is invalid. for example going TO 10 FROM 21 there is no way on the subtraction process you'll ever get a difference of 10 on both checks(NW and NE directions)

Now checking for exceeding a "wall"...

if you take a look at the picture below, you can see we start at cell 21. for example we go to cell 18. We can see that there is a block or "wall" on 20. To check this ambiguity. All you have to do is determine the start the by adding or subtracting from the current position until you arrived at the ending position while checking if the array has a flag of 1.

E.G.

from 21 going to 18.

1. 21 - 1 == 20 check array[20] if it's set to 1 if it's not, decrease further

2. Since 20 is set to 1 then the move is invalid...

It's complicated than first thought. I hope you understood what I've said. As long as you follow the rules I set above, I'm sure you can solve the problem.

The lines below shows the possible movements.

P.S. as for determining whether going E or W, this condition happens when the check for NW and NE or SE or SW doesn't conclude any match of the ending position.

I have not tested this on a program, there might be errors on something I've said... :) forgive me if there are errors or have not understood the problem. :grin:

Eko, here's a solution I thought up, but note it only works with your hexagon dimensions. I apologize for using pseudo-C code but I think ASM would make the post too large.

First create a 61x4 byte table cell array to store x,y,z,_ info for each hexagon cell.

Pseudo-C code:

Then you'll probably want a 61 byte array to hold board/player/piece data.

After that, moving pieces around is as simple as checking x, y, z.

I hope you understood that. I included a diagram to help visualize.

First create a 61x4 byte table cell array to store x,y,z,_ info for each hexagon cell.

Pseudo-C code:

```
[size=12]typedef struct {
```

char x;

char y;

char z;

char padding;

} XYZ;

XYZ cell_table[61];

int XYZtoCellIndex( char x, char y, char z )

{

return ( z > 4-y )

? (-(y*y)-(z*z)-(2*y*z)+(25*y)+(27*z)+(2*x)-32) >> 1

: ((y*y)+(z*z)+(2*y*z)+(9*y)+(11*z)+(2*x)) >> 1;

}

XYZ CellIndexToXYZ( int c )

{

XYZ t;

t.x = cell_table[c].x;

t.y = cell_table[c].y;

t.z = cell_table[c].z;

return t;

}

void GenerateTable( void )

{

int x, y, z, c;

ZeroMemory( cell_table, 61*4 );

for( z=0; z<5; z++ ){

for( y=0; y<5; y++ ){

for( x=0; x<5; x++ ){

c = XYZtoCellIndex(x,y,z);

cell_table[c].x = x;

cell_table[c].y = y;

cell_table[c].z = z;

}}}

}[/size]

Then you'll probably want a 61 byte array to hold board/player/piece data.

After that, moving pieces around is as simple as checking x, y, z.

```
[size=12]bool isPathClear_X( int cell, int relative_x )
```

{

int i;

int c, bd;

XYZ t = CellIndexToXYZ( cell );

if ((t.x + relative_x) < 0) || ((t.x + relative_x) > 4)

return false;

for( i=1; i <= abs(relative_x); i++ )

{

c = XYZtoCellIndex((relative_x<0)?t.x-i:t.x+i,t.y,t.z);

if( board_data[c] & FLAG_OCCUPIED )

return false;

}

return true;

}

bool isPathClear_Y( int cell, int relative_y );

bool isPathClear_Z( int cell, int relative_z );[/size]

I hope you understood that. I included a diagram to help visualize.

Now that I look at it, you could just use the .padding element of the xyz struct to hold board data.

hiii

thanks for the ideas.. if some of you have more ideas. please continue give them.

iblis:can you explain alittle how does it work ?

and what is : and ?

i thought on my own idea . it doesnt work . maybe you can help me fix it

i have array of all the free spaces in the board

so i thought maybe i'lll do Recorsiv to check the way . but it doesnt work .. i have mistake and icant find it

thanks

eko

thanks for the ideas.. if some of you have more ideas. please continue give them.

iblis:can you explain alittle how does it work ?

and what is : and ?

i thought on my own idea . it doesnt work . maybe you can help me fix it

i have array of all the free spaces in the board

so i thought maybe i'lll do Recorsiv to check the way . but it doesnt work .. i have mistake and icant find it

```
```

RecorsivCanWalk proc ;cell:BYTE

;cmp found,1

;je @finish

mov bl,byte ptr [esp+4] ;save alot of push ebp pop ebx . stack size

cmp bl,towhere

je @finish

cmp bl,fromwhere

jne @F

mov found,2

jmp @didntfind

@@:

invoke IsItThere

jc @didntfind

mov ebx,[esp+4];cell

add bl,9

push ebx

call RecorsivCanWalk

cmp found,0

jnz @finish

;invoke RecorsivCanWalk,bl

mov ebx,[esp+4];cell

dec bl

push ebx

call RecorsivCanWalk

cmp found,0

jnz @finish

;invoke RecorsivCanWalk,bl

mov ebx,[esp+4];cell

sub bl,10

push ebx

call RecorsivCanWalk

cmp found,0

jnz @finish

;invoke RecorsivCanWalk,bl

mov ebx,[esp+4];cell

sub bl,9

push ebx

call RecorsivCanWalk

cmp found,0

jnz @finish

;invoke RecorsivCanWalk,bl

mov ebx,[esp+4];cell

inc bl

push ebx

call RecorsivCanWalk

cmp found,0

jnz @finish

;invoke RecorsivCanWalk,bl

mov ebx,[esp+4];cell

add bl,10

push ebx

call RecorsivCanWalk

;cmp found,1

;je @finish

; invoke RecorsivCanWalk,bl

@didntfind:

ret 4

@finish:

mov found,1

ret 4

RecorsivCanWalk endp

thanks

eko

Here's a working C version that uses depth-first search to find a path. This won't always find the shortest path, but will tell you whether a path can be found or not.

The

Here's the result:

It looks a bit strange but the +-signs show the path found. The numbers are the tiles visited. I've attached the compiled program.

Thomas

```
```

[size=9]#define arrcount(x) (sizeof(x)/sizeof(x[0]))

/*

char board[] = "-----0000"

"------000"

"-------00"

"--------0"

"---------0"

"--------00"

"-------000"

"------0000"

"-----";

*/

char board[] = "#----0000"

"###-#-000"

"#---###00"

"#-######0"

"---------0"

"#######-00"

"-#-#---000"

"#-#-##0000"

"--#--";

#define BOARDSIZE 81

char boardFormat[] = " . . . . .\n"

" . . . . . .\n"

" . . . . . . .\n"

" . . . . . . . .\n"

". . . . . . . . .\n"

" . . . . . . . .\n"

" . . . . . . .\n"

" . . . . . . \n"

" . . . . .\n";

int neighbourOffsets[] = {-10,-9,-1,+1,+9,+10};

bool isValidIndex(int index)

{

if (index<0 || index>=BOARDSIZE) return false;

return board[index]!='0';

}

int findNextNeighbour(int curPos, int prevNeighbour)

{

bool bPrevNeighbourFound = false;

for (int i=0;i<arrcount(neighbourOffsets);i++)

{

int curNeighbour = curPos + neighbourOffsets[i];

if (isValidIndex(curNeighbour))

{

if (prevNeighbour==-1) return curNeighbour;

if (curNeighbour==prevNeighbour)

{

bPrevNeighbourFound = true;

}

else if (bPrevNeighbourFound)

{

return curNeighbour;

}

}

}

return -1;

}

void printBoard()

{

char buffer[arrcount(boardFormat)];

int iBoard = 0;

for (int i=0;i<arrcount(boardFormat);i++)

{

if (boardFormat[i]=='.')

{

while (board[iBoard]=='0') iBoard++;

buffer[i] = board[iBoard];

iBoard++;

}

else

{

buffer[i] = boardFormat[i];

}

}

printf(buffer);

}

bool possiblePath(int curPos, int destPos, int trace[], int curDepth = 0)

{

trace[curDepth] = curPos;

if (curPos==destPos)

{

printf("path found!\n");

return true;

}

int prevNeighbour = -1;

int curNeighbour;

while(true)

{

curNeighbour = findNextNeighbour(curPos, prevNeighbour);

if (curNeighbour==-1) break; // done all neighbours

if (board[curNeighbour]=='-') //free piece?

{

// see if neighbour was already visited earlier:

bool bNeighbourVisited = false;

for (int k=0;k<curDepth;k++)

{

if (trace[k]==curNeighbour)

{

bNeighbourVisited = true;

break;

}

}

if (!bNeighbourVisited)

{

if (possiblePath(curNeighbour, destPos, trace, curDepth+1))

{

return true;

}

}

}

prevNeighbour = curNeighbour;

}

trace[curDepth] = -1;

return false;

}

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

{

printf("legenda:\n\n"

"-\tfree space\n"

"#\tused space\n"

"+\tpart of the found path\n\n");

int trace[BOARDSIZE+1];

for (int i=0;i<arrcount(trace);i++) trace[i] = -1;

printf("Board:\n");

printBoard();

if (possiblePath(1, 79, trace))

{

printf("Found path:\n");

int k=0;

while(true)

{

int j = trace[k];

if (j==-1) break;

printf(" %d", j);

board[j] = '+';

k++;

}

printf("\n");

printBoard();

}

else

{

printf("no path found!\n");

}

return 0;

}

[/SIZE]

The

**board**array contains the board data ('0' = invalid index, '-' = free space, '#' (or anything else) = used space). The code will try to find a path from index 1 to index 79 and show it.Here's the result:

```
```

legenda:

- free space

# used space

+ part of the found path

Board:

# - - - -

# # # - # -

# - - - # # #

# - # # # # # #

- - - - - - - - -

# # # # # # # -

- # - # - - -

# - # - # #

- - # - -

path found!

Found path:

1 2 3 12 21 20 19 28 37 38 39 40 41 42 43 44 53 62 61 60 69 79

# + + + -

# # # + # -

# + + + # # #

# + # # # # # #

- + + + + + + + +

# # # # # # # +

- # - # + + +

# - # + # #

- - # + -

It looks a bit strange but the +-signs show the path found. The numbers are the tiles visited. I've attached the compiled program.

Thomas

**and what is : and ?**

"?" and ":" in C are part of conditional expression.

is exactly the same as...

"?" and ":" in C are part of conditional expression.

*a += ( b < 4 ) ? b : 1;*is exactly the same as...

*if( b < 4 )*

{ a = a + b; }

else

{ a = a + 1 }{ a = a + b; }

else

{ a = a + 1 }

**iblis:can you explain alittle how does it work ?**

Basically what you'd be doing is assigning each hexagon-cell an x,y,z value so that you can easily traverse each direction of the board. By incrementing/decrementing either x, y or z and then translating that value to its array index, you can check if a hexagon-cell in a certain direction is occupied/moveable. How you do this is unimportant as long as you have some way of translating x,y,z to its corresponding cell.

In the diagram below I changed the rules a bit. x, y, and z diverge outward from the center. This way you can easily adjust the size of the board if you want. ( The number of cells on a board like this is 3r?-3r+1 where

Note that in each cell in the diagram, z = y - x, so you really only need to store x and y.Basically what you'd be doing is assigning each hexagon-cell an x,y,z value so that you can easily traverse each direction of the board. By incrementing/decrementing either x, y or z and then translating that value to its array index, you can check if a hexagon-cell in a certain direction is occupied/moveable. How you do this is unimportant as long as you have some way of translating x,y,z to its corresponding cell.

In the diagram below I changed the rules a bit. x, y, and z diverge outward from the center. This way you can easily adjust the size of the board if you want. ( The number of cells on a board like this is 3r?-3r+1 where

**r**is the number of cells from the center to any corner. )Note that in each cell in the diagram, z = y - x, so you really only need to store x and y.

**
**

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?

I don't see anything special about it. :confused:Well, it would take some time for me to make that image in the software I have here. Surely a sign of your illustrative skills! I have M$ Visio for illustrative stuff - it has paid for itself a couple times over. It is similar to Excel - good for many things, great for nothing. When you can't afford much software, but want to do a variety of things - it is a good purchase.

Thomas
Thomas : thanks!

i think i have done the same . or closer

i have wrote a function that insert into an array all the freeplaces

and then search in recursiv for the destinion while adding (-9,1,10,-9,-1,10)

until it finds

so it doesnt search for the shortest way just check if there is one

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?

thanks all

bye

eko

i think i have done the same . or closer

i have wrote a function that insert into an array all the freeplaces

and then search in recursiv for the destinion while adding (-9,1,10,-9,-1,10)

until it finds

so it doesnt search for the shortest way just check if there is one

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?

thanks all

bye

eko

hiiii

i forgot to publish my game

i made it for an Israel Computer contest that the prize of the contest is some "money ticket to an Computer shop in here"

here is it

a made the board in an array of 9 on9

so i can more easly access other cells

its like

x-10 x - 9

x- 1 x x + 1

x+9 x - 9

there is a loss of 81-61 bytes

but i used someof those lost bytes as a varibles

this way has been done only becuase i had very little time to work on the game ...

if I build such a game with more time . place the board in 61 bytes array and not 81

but

any away

bye

eko

stop talking / writing

EDIT:

there are some crazy thing in there becuase the lack of time .

and its not finish

so dont pay attention

i forgot to publish my game

i made it for an Israel Computer contest that the prize of the contest is some "money ticket to an Computer shop in here"

here is it

a made the board in an array of 9 on9

so i can more easly access other cells

its like

x-10 x - 9

x- 1 x x + 1

x+9 x - 9

there is a loss of 81-61 bytes

but i used someof those lost bytes as a varibles

this way has been done only becuase i had very little time to work on the game ...

if I build such a game with more time . place the board in 61 bytes array and not 81

but

any away

bye

eko

stop talking / writing

EDIT:

there are some crazy thing in there becuase the lack of time .

and its not finish

so dont pay attention

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?

**iblis**, ?C?mo usted hace estos picuters?

Erm, eh... The same way anybody else makes 'em. Any graphics program would do it, Photoshop, Illustrator etc. Heck MS Paint could do it.

I don't see anything special about it. :confused:

I don't see anything special about it. :confused:

I don't see anything special about it. :confused:

**eko**, I think you forgot to preserve esi/edi/ebx somewhere. The game kept crashing on my win2k machine until I added uses esi edi ebx to WndProc..

Thomas