Re: Search Algorithm - Algorithms Discussion Boards

Cyclone_S16-Apr-11 8:22

16-Apr-11 8:22

Hi, I am coding an algorithm that searches for a box on the screen. So far I got the snake to find the food which works great except that for example. If the snake is moving right it will sometimes move left and move ontop of it's self. I've spent awhile trying to figure it out on my own with no success. I think it has to do with the two blocks of if statements but I'm not sure. Maybe they need to be combined somehow? This is the last thing I need to figure out and my program is finished. Thanks in advance.

I tried.

if(direction_comp!=1){direction_comp=-1;} else {direction_comp=2;}  // If snake is not moving left then move it right else move it up to avoid it from moving on top of it's self.

direction_comp of 1 = left;
direction_comp of -1 = right;
direction_comp of 2 = up;
direction_comp of -2 = down;

void comp_direction()
			{

				if(tick_comp==0 && avoiding==false)
				{
				if(segments_comp[head_comp]->panel->Left <= Food->Left)
				{	
					if(segments_comp[head_comp]->panel->Top >= Food->Top){direction_comp =2;}
					else{direction_comp=-1;}
				}
				else if(segments_comp[head_comp]->panel->Left >= Food->Left)
				{	
					if(segments_comp[head_comp]->panel->Top >= Food->Top){direction_comp =2;}
					else{direction_comp=1;}

				}
				if(segments_comp[head_comp]->panel->Top <= Food->Top)
				{
					if(segments_comp[head_comp]->panel->Left <= Food->Left){direction_comp =-1;}
					else{direction_comp=-2;}
					
				}
				else if(segments_comp[head_comp]->panel->Top >= Food->Top)
				{
					if(segments_comp[head_comp]->panel->Left >= Food->Left){direction_comp =1;}
					else{direction_comp=2;}
				}
				}
			}

Re: Search Algorithm

bob1697216-Apr-11 9:28

bob16972

16-Apr-11 9:28

First off, there appears to be some redundant checks in the "else if" lines. Unless I'm missing something, the "if" portion of the "else if" will always be true since the "else" implies the converse of the "<=" operator from the original "if" block.

Now this won't effect the outcome of the snippet you posted but removing it and formatting it with some slightly different indentation and a few constant symbols might be easier to read in order to understand your implementation. If one took the liberty to do this, without impacting the logic, it might look like this...

const int LEFT = 1;
const int RIGHT	= -1;
const int UP = 2;
const int DOWN = -2;


void comp_direction()
{
	if (tick_comp == 0 && avoiding == false) {
		if (segments_comp[head_comp]->panel->Left <= Food->Left) {


			if (segments_comp[head_comp]->panel->Top >= Food->Top) {
				direction_comp = UP;
			} else {
				direction_comp = RIGHT;
			}


		} else {

			if (segments_comp[head_comp]->panel->Top >= Food->Top) {
				direction_comp = UP;
			} else {
				direction_comp = LEFT;
			}
		}

		/*
		This section will always run, effectively overwriting
		the direction_comp value from above. Is this by design?
		*/
		if (segments_comp[head_comp]->panel->Top <= Food->Top) {


			if (segments_comp[head_comp]->panel->Left <= Food->Left) {
				direction_comp = RIGHT;
			} else { 
				direction_comp = DOWN;
			}
			
		} else {

			if (segments_comp[head_comp]->panel->Left >= Food->Left) {
				direction_comp = LEFT;
			} else { 
				direction_comp = UP;
			}
		}
	}
}

You did not really provide much detail about your algorithm so I'm afraid I can't help much but I must ask, did you intend for the code to keep overwriting "direction_comp" even if it had been assigned earlier in the method?

Re: Search Algorithm

Cyclone_S16-Apr-11 13:10

Cyclone_S

16-Apr-11 13:10

No I didn't intend for the code to overwrite "direction_comp". That's the part I need help with. What the code does is make a snake home in on a food box. It works but sometimes the snake moves backwards on it's self. I think I know how to code that part but it won't work cuzz "direction_comp" keeps getting overwritten from the previous if block.

Re: Search Algorithm

bob1697216-Apr-11 17:52

bob16972

16-Apr-11 17:52

Well, the collision detection looks a little confusing since your comparing edges of rectangles. I'd use a combination of center points and intersection detection based (or some grid based 2d cell array like the old atari 2600 games used to use) on what I can make out of what you've posted. However, I'll ignore those particulars and focus on the single question I think you are asking.

As far as the logic is concerned, if you only want to set a value and then exit the method, you wouldn't need the "else" blocks. This is only pseudocode but you could approach the need to break after an assignment like...

const int LEFT = 1;
const int RIGHT	= -1;
const int UP = 2;
const int DOWN = -2;


void comp_direction()
{
	if (tick_comp == 0 && avoiding == false) {


		if (panel is lower than food) { // But not level with it
			direction_comp = UP;
			return;
		}


		if (panel is higher than food) { // But not level with it
			direction_comp = DOWN;
			return;
		}


		if (panel is left of food) { // But not lined up with it
			direction_comp = RIGHT;
			return;
		}


		if (panel is right of food) { // But not level with it
			direction_comp = LEFT;
			return;
		}
	}
}

However, this isn't very entertaining to watch since it will always adjust vertically then home in horizontally. It also does not attempt to prevent movement over itself but since I don't have more knowledge of how your program is designed, I can't really offer too much help at this point.

If you want to provide more details, on the big picture and the design requirements, it might be easier for us to help.
Anyway, I hope that helps.

Re: Search Algorithm

Cyclone_S20-Apr-11 9:58

Cyclone_S

20-Apr-11 9:58

Thanks for taking the time to respond.

The snake is supposed to search for food and check if it collides with it's self. I spent a few days on this and I got it partially working but the snake still intersects with it's self in certain situations(see image). Do you see anything wrong with this code?

http://img163.imageshack.us/i/screengby.jpg/[^]

The first section the snake goes in the direction of the food.
The second section is the code that checks for colision.

left = 1
right = -1
up = 2
down = -2

void comp_direction()
			{
	
				
				// Make The Snake Search For Food
				int test = direction_comp;

				if(segments_comp[head_comp]->panel->Top <= Food->Top)
				{
					if(segments_comp[head_comp]->panel->Left > Food->Left){direction_comp = -2;} else{direction_comp=-1;}

				}
				else
				{	
					if(segments_comp[head_comp]->panel->Left < Food->Left){direction_comp =2;}else{direction_comp=1;}

				}

				


				// Check for Computer Body Collision
				if(direction_comp==1)
				{
					for(int I=0;I<(size_comp-1);I++) // Coliding Left
					{
						if(head_comp2->Left == segments_comp[I]->panel->Right && head_comp2->Top == segments_comp[I]->panel->Top)
						{
							for(int I=0;I<(size_comp-1);I++) // Coliding Left
							{
								if(head_comp2->Bottom == segments_comp[I]->panel->Top && head_comp2->Left == segments_comp[I]->panel->Left) // Coliding Left Bottom Corner
								{direction_comp = 2;break;}
								else if(head_comp2->Top == segments_comp[I]->panel->Bottom && head_comp2->Left == segments_comp[I]->panel->Left) // Coliding Left Top Corner
								{direction_comp = -2;break;}
								else {direction_comp = 2;} // Coliding Left (will be random)
							}
						}
					}
				}

				else if(direction_comp==-1)
				{
					for(int I=0;I<(size_comp-1);I++) // Coliding Right
					{
						if(head_comp2->Right == segments_comp[I]->panel->Left && head_comp2->Top == segments_comp[I]->panel->Top)
						{
							for(int I=0;I<(size_comp-1);I++)
							{
								if(head_comp2->Top == segments_comp[I]->panel->Bottom && head_comp2->Left == segments_comp[I]->panel->Left) // Coliding Left Top Corner
								{direction_comp = -2;break;}
								else if(head_comp2->Bottom == segments_comp[I]->panel->Top && head_comp2->Left == segments_comp[I]->panel->Left) // Coliding Left Bottom Corner
								{direction_comp = 2;break;}
								else{direction_comp =2;} // Coliding Right (will be random)
							}
						}
					}
				}

				else if(direction_comp==2)
				{
					for(int I=0;I<(size_comp-1);I++) // Coliding Up
					{
						if(head_comp2->Top == segments_comp[I]->panel->Bottom && head_comp2->Left == segments_comp[I]->panel->Left)
						{
							for(int I=0;I<(size_comp-1);I++) 
							{
								if(head_comp2->Right == segments_comp[I]->panel->Left && head_comp2->Top == segments_comp[I]->panel->Top) // Coliding Up Right Corner
								{direction_comp = 1;break;}
								else if(head_comp2->Left == segments_comp[I]->panel->Right && head_comp2->Top == segments_comp[I]->panel->Top) // Coliding Up Left Corner
								{direction_comp = -1;break;}
								else{direction_comp = -1;} // Coliding Top (will be random)
							}
							
						}
					}
				}

				else if(direction_comp==-2)
				{
					for(int I=0;I<(size_comp-1);I++) // Coliding Down
					{
						if(head_comp2->Bottom == segments_comp[I]->panel->Top && head_comp2->Left == segments_comp[I]->panel->Left)
						{
							for(int I=0;I<(size_comp-1);I++) // Coliding Down
							{
								if(head_comp2->Right == segments_comp[I]->panel->Left && head_comp2->Top == segments_comp[I]->panel->Top) // Colliding Right Bottom Corner
								{direction_comp =1;break;}
								else if(head_comp2->Left == segments_comp[I]->panel->Right && head_comp2->Top == segments_comp[I]->panel->Top) // Colliding Left Bottom Corner
								{direction_comp =-1;break;}
								else {direction_comp =1;} // Coliding Down (will be random)
							}
						}
					}
				}


				
				if(test==1 && direction_comp==-1){direction_comp=2;}
				else if(test==-1 && direction_comp==1){direction_comp=2;}
				else if(test==2 && direction_comp==-2){direction_comp=1;}
				else if(test==-2 && direction_comp==2){direction_comp=1;}
				
			}

Re: Search Algorithm

bob1697220-Apr-11 18:06

bob16972

20-Apr-11 18:06

Lets step back from this a minute and contemplate any brickwalls that need to be thought through before coding (I always do this at work before spending any real time coding)

Your current algorithm assumes that there is only one food item at any given time. Lets just say you've coded the snake to be attracted to the food and home in on it. Once it eats the food, it grows one segment larger and another piece of food appears at some random location on the grid. The snake could be in a position to wrap into itself and it's own collision avoidance algorithm could cause it to spiral into a tight knot and ultimately cause a dead end for your algorithm.

With that said, how do you intend to avoid that situation? This will likely influence your overall collision avoidance algorithm.

Re: Search Algorithm

Cyclone_S21-Apr-11 14:45

Cyclone_S

21-Apr-11 14:45

I don't tend to avoid it, I just want to get it working the way it is. Easier that way then trying to figure out something more complex.

Re: Search Algorithm

Cyclone_S22-Apr-11 9:57

Cyclone_S

22-Apr-11 9:57

I think my previous aproach is not working becuase the position of the segments isn't pixel perfect so the snake slips through and goes in the wrong direction.

I'm currently trying a different aproach which puts 3 boxes around the snake. One on the left, on the right and one on the top(see image). The code checks if one of those boxes touches a segment of the snake and then prevents the snake from going in the wrong direction. It works better but it still goes in the wrong direction some times when it's in a corner. Maybe because the if statements aren't in the correct order?

I attached the source code, and a release build(choose game type3 and press right arrow). Maybe you can find something wrong with the code. The functions related to the computer snake algorithm are Timer1,void comp_direction() and void move_comp_snake(). The code is pretty messy and long so you would have to do a search for those functions.

http://inspiredvisuals.com/Release-source.zip[^]

http://img863.imageshack.us/i/image2n.jpg/[^]

direction_comp values:
Left=1
Right=-1
Up=2
Down=-1

Here is a portion of the code. Maybe the if statements aren't in the correct order? I checked a few times and don't see a problem. It uses loops. One for each side of the snake and sets bool variables to true if one of the boxes touches a segment of the snake. It then uses a bunch of if staments to tell the snake to go in the correct direction depending on certain conditions such as the previous direction or if it runs into a corner.

int temp = direction_comp; //Used to prevent the snake from moving backwards.
				
				// Variables used to check for collisions.
				bool colide_left = false;
				bool colide_right = false;
				bool colide_top = false;
				bool colide_bottom = false;

				// Make The Snake Search For Food
				if(segments_comp[head_comp]->panel->Top <= Food->Top)
				{
					if(segments_comp[head_comp]->panel->Left > Food->Left){direction_comp = -2;} else{direction_comp=-1;}
				}
				else
				{	
					if(segments_comp[head_comp]->panel->Left < Food->Left){direction_comp =2;}else{direction_comp=1;}
				}

				// Check for snake body collision.
				if(direction_comp==2) // Moving Up
				{
					for(int I=0;I<(size_comp-1);I++) // Coliding Top
					{
						if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) ||  (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
						{
							if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
							{colide_top = true;break;}
						}
						else if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
						{
							if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) || (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
							{colide_top = true;break;}
						}
					}

					for(int I=0;I<(size_comp-1);I++) // Coliding Top Right Corner
					{
						if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) ||  (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
						{
							if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
							{colide_right = true;break;}
						}
						else if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
						{
							if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) || (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
							{colide_right = true;break;}
						}
					}

					for(int I=0;I<(size_comp-1);I++) // Coliding Top Left Corner
					{
						if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) ||  (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
						{
							if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
							{colide_left = true;break;}
						}
						else if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
						{
							if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) || (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
							{colide_left = true;break;}
						}
					}
						if(colide_top == true && colide_left == true && colide_right == true){Timer1->Stop();} // If snake gets trapped in a corner kill the snake.
						else if(colide_top == true && colide_right == true && previous_direction == 1){direction_comp = -2;} // If snake was moving left and is in left top corner.
						else if(colide_top == true && colide_left == true && previous_direction == -1){direction_comp = -2;} // If snake was moving right and is in right top corner.
						else if(colide_right == true && previous_direction == 1){direction_comp = 1;} // If snake is directly undernieth its's body and moving left prevent snake from moving up.
						else if(colide_left == true && previous_direction == -1){direction_comp = -1;} // If snake is directly undernieth its's body and moving right prevent snake from moving up.
						else if(colide_top == true && colide_left == true){direction_comp = -1;} // If snake is moving up and is coliding with top left corner.
						else if(colide_top == true && colide_right == true){direction_comp = 1;} // If snake is moving up and is coliding with top right corner.
						else if(colide_top == true){direction_comp = 1;} // Coliding Top (will be random)
						
						
				}

// Prevent the snake from moving backwards.
				if(temp==1 && direction_comp==-1){direction_comp=2;}
				else if(temp==-1 && direction_comp==1){direction_comp=2;}
				else if(temp==2 && direction_comp==-2){direction_comp=1;}
				else if(temp==-2 && direction_comp==2){direction_comp=1;}

				previous_direction = direction_comp; // Store the previous direction.

The entire function.

void comp_direction()
{
    int temp = direction_comp; //Used to prevent the snake from moving backwards.

    // Variables used to check for collisions.
    bool colide_left = false;
    bool colide_right = false;
    bool colide_top = false;
    bool colide_bottom = false;

    // Make The Snake Search For Food
    if(segments_comp[head_comp]->panel->Top <= Food->Top)
    {
        if(segments_comp[head_comp]->panel->Left > Food->Left){direction_comp = -2;} else{direction_comp=-1;}
    }
    else
    {
        if(segments_comp[head_comp]->panel->Left < Food->Left){direction_comp =2;}else{direction_comp=1;}
    }

    // Check for snake body collision.
    if(direction_comp==2) // Moving Up
    {
        for(int I=0;I<(size_comp-1);I++) // Coliding Top
        {
            if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) ||  (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_top = true;break;}
            }
            else if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) || (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
                {colide_top = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Top Right Corner
        {
            if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) ||  (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_right = true;break;}
            }
            else if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) || (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
                {colide_right = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Top Left Corner
        {
            if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) ||  (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_left = true;break;}
            }
            else if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) || (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
                {colide_left = true;break;}
            }
        }
            if(colide_top == true && colide_left == true && colide_right == true){Timer1->Stop();} // If snake gets trapped in a corner kill the snake.
            else if(colide_top == true && colide_right == true && previous_direction == 1){direction_comp = -2;} // If snake was moving left and is in left top corner.
            else if(colide_top == true && colide_left == true && previous_direction == -1){direction_comp = -2;} // If snake was moving right and is in right top corner.
            else if(colide_right == true && previous_direction == 1){direction_comp = 1;} // If snake is directly undernieth its's body and moving left prevent snake from moving up.
            else if(colide_left == true && previous_direction == -1){direction_comp = -1;} // If snake is directly undernieth its's body and moving right prevent snake from moving up.
            else if(colide_top == true && colide_left == true){direction_comp = -1;} // If snake is moving up and is coliding with top left corner.
            else if(colide_top == true && colide_right == true){direction_comp = 1;} // If snake is moving up and is coliding with top right corner.
            else if(colide_top == true){direction_comp = 1;} // Coliding Top (will be random)


    }
    else if(direction_comp==-2) // Moving Down
    {
        for(int I=0;I<(size_comp-1);I++) // Coliding Bottom
        {
            if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) ||  (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_bottom = true;break;}
            }
            else if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) || (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
                {colide_bottom = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Top Left Corner
        {
            if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) ||  (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_left = true;break;}
            }
            else if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) || (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
                {colide_left = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Top Right Corner
        {
            if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) ||  (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_right = true;break;}
            }
            else if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) || (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
                {colide_right = true;break;}
            }
        }

            if(colide_bottom == true && colide_left == true && colide_right == true){Timer1->Stop();} // If snake gets trapped in a corner kill the snake.
            else if(colide_bottom == true && colide_right == true && previous_direction == 1){direction_comp = 2;} // If snake was moving left and is in left bottom corner.
            else if(colide_bottom == true && colide_left == true && previous_direction == -1){direction_comp = 2;} // If snake was moving right and is in right bottom corner.
            else if(colide_right == true && previous_direction == 1){direction_comp = 1;} // If snake is directly above its's body and moving left prevent snake from moving down.
            else if(colide_left == true && previous_direction == -1){direction_comp = -1;} // If snake is directly above its's body and moving right prevent snake from moving down.
            else if(colide_bottom == true && colide_left == true){direction_comp = -1;} // If snake is moving down and is coliding with bottom left corner.
            else if(colide_bottom == true && colide_right == true){direction_comp = 1;} // If snake is moving down and is coliding with bottom right corner.
            else if(colide_bottom == true){direction_comp = 1;} // Coliding bottom (will be random).



    }
    else if(direction_comp == 1) // Moving Left
    {
        for(int I=0;I<(size_comp-1);I++) // Coliding Left
        {
            if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) ||  (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_left = true;break;}
            }
            else if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) || (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
                {colide_left = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Left Top Corner
        {
            if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) ||  (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_top = true;break;}
            }
            else if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) || (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
                {colide_top = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Left Bottom Corner
        {
            if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) ||  (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_bottom = true;break;}
            }
            else if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) || (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
                {colide_bottom = true;break;}
            }
        }

            if(colide_top == true && colide_bottom == true && colide_left == true){Timer1->Stop();} // If snake gets trapped in a corner kill the snake.
            else if(colide_bottom == true && colide_left == true && previous_direction == -2){direction_comp = -1;} // If snake was moving up and is in left top corner.
            else if(colide_top == true && colide_left == true && previous_direction == -2){direction_comp = -1;} // If snake was moving down and is in left bottom corner.
            else if(colide_bottom == true && previous_direction == 2){direction_comp = 2;} // If snake is directly to the right of its's body and moving up prevent snake from moving left.
            else if(colide_top == true && previous_direction == -2){direction_comp = -2;} // If snake is directly to the right its's body and moving down prevent snake from moving left.
            else if(colide_top == true && colide_left == true){direction_comp = -2;} // If snake is moving left and is coliding with top left corner.
            else if(colide_bottom == true && colide_left == true){direction_comp = 2;} // If snake is moving left and is coliding with bottom left corner.
            else if(colide_left == true){direction_comp = 1;} // Coliding Top (will be random)



    }
    else if(direction_comp==-1) // Moving Right
    {
        for(int I=0;I<(size_comp-1);I++) // Coliding Right
        {
            if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) ||  (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_right = true;break;}
            }
            else if((head_comp2->Top >= segments_comp[I]->panel->Top && head_comp2->Top <= segments_comp[I]->panel->Bottom) || (head_comp2->Bottom >= segments_comp[I]->panel->Top && head_comp2->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp2->Right >= segments_comp[I]->panel->Left && head_comp2->Right <= segments_comp[I]->panel->Right) || (head_comp2->Left >= segments_comp[I]->panel->Left && head_comp2->Left <= segments_comp[I]->panel->Right))
                {colide_right = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Right Bottom Corner
        {
            if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) ||  (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_bottom = true;break;}
            }
            else if((head_comp3->Top >= segments_comp[I]->panel->Top && head_comp3->Top <= segments_comp[I]->panel->Bottom) || (head_comp3->Bottom >= segments_comp[I]->panel->Top && head_comp3->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp3->Right >= segments_comp[I]->panel->Left && head_comp3->Right <= segments_comp[I]->panel->Right) || (head_comp3->Left >= segments_comp[I]->panel->Left && head_comp3->Left <= segments_comp[I]->panel->Right))
                {colide_bottom = true;break;}
            }
        }

        for(int I=0;I<(size_comp-1);I++) // Coliding Right Top Corner
        {
            if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) ||  (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
            {
                if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
                {colide_top = true;break;}
            }
            else if((head_comp4->Top >= segments_comp[I]->panel->Top && head_comp4->Top <= segments_comp[I]->panel->Bottom) || (head_comp4->Bottom >= segments_comp[I]->panel->Top && head_comp4->Bottom <= segments_comp[I]->panel->Bottom))
            {
                if((head_comp4->Right >= segments_comp[I]->panel->Left && head_comp4->Right <= segments_comp[I]->panel->Right) || (head_comp4->Left >= segments_comp[I]->panel->Left && head_comp4->Left <= segments_comp[I]->panel->Right))
                {colide_top = true;break;}
            }
        }

            if(colide_top == true && colide_bottom == true && colide_right == true){Timer1->Stop();} // If snake gets trapped in a corner kill the snake.
            else if(colide_bottom == true && colide_right == true && previous_direction == 2){direction_comp = 1;} // If snake was moving up and is in right top corner.
            else if(colide_top == true && colide_right == true && previous_direction == -2){direction_comp = -1;} // If snake was moving down and is in right bottom corner.
            else if(colide_bottom == true && previous_direction == 2){direction_comp = 2;} // If snake is directly to the left of its's body and moving up prevent snake from moving right.
            else if(colide_top == true && previous_direction == -2){direction_comp = -2;} // If snake is directly to the left of its's body and moving down prevent snake from moving right.
            else if(colide_top == true && colide_right == true){direction_comp = -2;} // If snake is moving right and is coliding with top right corner.
            else if(colide_bottom == true && colide_right == true){direction_comp = 2;} // If snake is moving right and is coliding with bottom right corner.
            else if(colide_right == true){direction_comp = 1;} // Coliding right (will be random)

    }

    // Prevent the snake from moving backwards.
    if(temp==1 && direction_comp==-1){direction_comp=2;}
    else if(temp==-1 && direction_comp==1){direction_comp=2;}
    else if(temp==2 && direction_comp==-2){direction_comp=1;}
    else if(temp==-2 && direction_comp==2){direction_comp=1;}

    previous_direction = direction_comp; // Store the previous direction.

}

Re: Search Algorithm

bob1697224-Apr-11 4:59

bob16972

24-Apr-11 4:59

First off, I didn't vote your last post down. However, I think the brute force approach is not panning out for you here as your logic and code have become somewhat complicated to follow, even for a veteran programmer.

I mentioned earlier a different approach and I'd recommend entertaining the thought that you might have to step back, regroup, and revisit the problems at hand, one at a time (as opposed to all in the same method).

Assumptions about your algorithm...
1) Snake segments and head are all the same size, and each is rectangular.
2) Only one food item will be present at any given moment, and is rectangular.
3) Snake head and segment size is not necessarily the same size as the food item.
4) Collision avoidance should prevent the snake from running through itself.
5) The world coordinate space has no outer boundaries (walls) that we need to be concerned with at the moment.
6) Diagonal movement is allowed.
7) Snake head and body segments are stored in some type of collection.

Ideas on determining direction...
1) Compare the center point of the food rectangle to the center point of the snake head to determine the x and y bias for movement. This should be recalculated each time and the x and y preferred directions should be stored separately.

2) Compute a separate vertical intersection and a separate horizontal intersection for the head and the food to tell you when you would be inline with the food with respect to a particular axis. Since the rectangles might not be the same si ze, this can be used in combination with the centerpoint comparison to prevent constantly jumping back and forth over the center point line as you approach the food.

For example if the y bias is up, but the vertical intersection is not empty, it means you don't need to adjust your vertical direction for this next move. Same goes with the x direction. If both the x and y intersections are not empty, this indicates you've stumbled upon the food. You either end the animation or randomize a new location for a new piece of food and start again after addinga segment to the snake.

3) Start a loop that first checks the full intersection of the proposed head position with each body segment. If the rectangular intersection of any body segment is not empty, the proposed next position is not acceptable and an alternate route will need to be obtained. You would then choose to randomize the next direction choice while keeping track of the possible next steps and the ones you've already tried so that you can detect a stalemate condition (such as wrapping into yourself or something that prevents any legal moves), otherwise it will loop endlessly.

If you determine there is a valid next move, take it and exit this particular loop and repeat the process, starting at step one.

********************************
Again, in a nutshell, the steps are...
1) Which way do you want to go?
2) Which way do you need to go?
3) If you don't get what you want, try a slightly different path.
4) Repeat if necessary.

There are some many variations you can make to this to make it more entertaining but I'm more focused on you coding these steps in multiple methods. Don't try and pack it all into one method.

Prefer to use symbols so we don't have to remember what 1, 2, -1, -2 means...

const int LEFT = 1;
const int RIGHT	= -1;
const int UP = 2;
const int DOWN = -2;
			if (something) {
				direction_comp = UP;
			} else {
				direction_comp = LEFT;
			}

Re: Search Algorithm

Cyclone_S27-Apr-11 13:43

Cyclone_S

27-Apr-11 13:43

Thanks for taking the time to reply and for the advice. I agree my coding is a really messy and needs a re-write. Frown | :(

Re: Search Algorithm

Luc Pattyn20-Apr-11 12:39

Luc Pattyn

20-Apr-11 12:39

IMO you should come up with a valid algorithm before you start coding; you may of course describe your algorithmic attempts in some kind of pseudo-code.

Here are a few requirement issues you should settle first:
- is the world a rectangle?
- are there any obstacles?
- can the snake SEE the food from a distance, or will it have to stumble upon it?
- is the snake length limited? could it exceed twice the smaller dimension of its world?

Depending on your requirements the algorithm may be quite different, or even unsolvable (without backtracking that is).

Example: if the snake could be longer than twice the height, it could corner itself when moving up (or down) close to an edge (say the right edge), and accidentally turning nearer to that edge (hence right) when reaching the top edge.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

Re: Search Algorithm

AspDotNetDev20-Apr-11 13:12

AspDotNetDev

20-Apr-11 13:12

Before I look too deeply into this, I thought I'd make an observation. Looks like you set "direction_comp" to 2 in three of four code blocks. Should one of those three be negative 2?

Chris Maunder wrote:
Fixign now.

But who's fixing the fixign?

Re: Search Algorithm

Cyclone_S20-Apr-11 13:40

Cyclone_S

20-Apr-11 13:40

Some are negative and some are positive. It depends on the direction the snake is moving.
If you can help me redesign the code I would be much apreciated. Maybe it would help if I post the program.

Re: Search Algorithm

Stefan_Lang26-Apr-11 4:32

Stefan_Lang

26-Apr-11 4:32

After looking at the full code you posted in a different branch, there are a few pieces of advice I'd like to give out:

(I) General coding advice

1. Don't put more than one statement on one line. It just makes the code harder to read. This does include control statements such as if or else, but not neccessarily tokens such as curly braces.

2. Don't use magic numbers. As others already pointed out, the constants -2, -1, 1, or 2 may be shorter to write, but they're also harder to read. Also, it's much easier to accidentally omit (or add) a '-' and thus swap an UP with DOWN or LEFT with RIGHT, than accidentally swapping symbols that actually say what they mean, rather than imply.

3. Don't write long functions. If your code (after reformatting according to item 1 above) is longer than ~50 lines it's about time to consider if you shouldn't split this function into multiple parts, or if there are repetitive parts in this function that you could extract into a separate function.

(II) 2D graphical coding advice

4. Don't encode a direction as a single number in a two-dimensional world. If you're traversing a linear array, then it makes sense to encode the direction you're moving in as -1 or 1. In 2D however it is much more practical to denote the X- and Y-components of your movement separately. It is quite easy to take the current position of an object, add to it the movement vector, and then compare it to the positions of objects that it might bump into. It's a lot more complicated to make if statements for each direction that you could move to, and it requires you to duplicate your code for every possible direction! (that is what you obviously did)

5. Provide a simple function or set of functions for collision checks between different types of shapes in your 2D-world. Apparently, snake segments, and food patches all occupy a rectangular box of a fixed size. Just define a struct called box that contains their position (x,y) and size (width, height); then define a function that checks two boxes for overlaps (or collision).

6. A somewhat more sophisticated system with 2D elements and collision checks can be found here. This goes beyond your requirements, but gives a very good insight into coding techniques for the kind of problems you're struggling with.

Re: Search Algorithm

Cyclone_S27-Apr-11 13:50

Cyclone_S

27-Apr-11 13:50

Thanks for the advice. I am a beginer coder and have lots of learning to do. Smile | :)

converting MFC program into web based

shiks11-Apr-11 17:06

shiks

11-Apr-11 17:06

dear madam,
will u plz tell me how to convert the MFC C++ application into .net application

Shrikant

Re: converting MFC program into web based

Albert Holguin11-Apr-11 18:13

Albert Holguin

11-Apr-11 18:13

don't know if there's an easy answer for this... but easiest way would be to convert to C++/CLI... either way you go, there will be a lot of work involved.

Re: converting MFC program into web based

shiks12-Apr-11 5:15

shiks

12-Apr-11 5:15

that application itself in c++ thats why

Re: converting MFC program into web based

Albert Holguin12-Apr-11 5:19

Albert Holguin

12-Apr-11 5:19

yeah but the infrastructure is completely different... that's why its a lot of work... almost like converting MFC application to Qt, a lot of work... there's always advantages/disadvantages of particular programming methodologies, this is a negative of using an existing infrastructure, converting it to another may be quite a bit of work.

Re: converting MFC program into web based

Albert Holguin12-Apr-11 5:21

Albert Holguin

12-Apr-11 5:21

if you HAVE to do it, your best bet will probably be to start a .net application from scratch and transfer over functionality a bit at a time, you'll essentially end up rewriting massive sections of code.

Re: converting MFC program into web based

Eddy Vluggen12-Apr-11 8:25

Eddy Vluggen

12-Apr-11 8:25

shiks wrote:
will u plz tell me how to convert the MFC C++ application into .net application

An MFC application runs in a completely different environment, has access to things like a printer and your webcam. Next problem is that browsers generally use HTML to display a UI, so this often hints towards a rewrite. Now, it would be hard to answer this question without any further information. Is it a large project? Used any COM-objects? Multithreading?

If it were a WinForm app, I'd say that the best option would be an interface to the most complex routines in the MFC-application and to P/Invoke the things you need from the .NET side of life. I guess ASP.NET would allow for something similar.

I are Troll Suspicious | :suss:

Re: converting MFC program into web based

shiks13-Apr-11 17:02

shiks

13-Apr-11 17:02

its not as big as project. its a genetic algorithm implemented on class scheduling and i want to implement it on practical time tabling system. i got that source code but making modification in it is tedius job. any one having genetic algorithm in c# so i could implement it in my work

Good way to detect a useful portion of equivalent expressions

David198718-Mar-11 0:00

David1987

18-Mar-11 0:00

I have to detect whether two given expressions are equivalent (both compute the same value for all inputs). The inputs will all be of simple types, such as int32, so it is theoretically possible to try all inputs and see whether the result are always the same.
That's too slow of course, so it will have to be done differently.

False positives are not acceptable at all.
False negatives are acceptable, but I need a useful amount of equivalences, so merely testing whether two expressions are equal does not solve the problem.

I have tried applying many transformations to one of the expressions and see whether they are ever equal, but that doesn't work very well. The False Negatives rate is still far too high to be useful.

Re: Good way to detect a useful portion of equivalent expressions

CPallini18-Mar-11 1:29

CPallini

18-Mar-11 1:29

Theoretically, if false positive are not acceptable then you have either to:

Analitically proof the equivalence.

Try all inputs.

My common sense suggests no escapes.
Smile | :)

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.

This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke

[My articles]

Re: Good way to detect a useful portion of equivalent expressions

David198718-Mar-11 1:41

David1987

18-Mar-11 1:41

But surely there are some shortcuts?
After all, false negatives are allowed, so the disjunction of a bunch of heuristic guestimates is OK as long as they are all pessimistic.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.