Search Algorithm

[bob16972]

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.

[Cyclone_S]

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 = -

[Luc Pattyn]

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. :)

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.

[AspDotNetDev]

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?

[Cyclone_S]

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.

[bob16972]

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.

[Cyclone_S]

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.

[Cyclone_S]

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

[bob16972]

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 stalem

[Stefan_Lang]

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.

[Cyclone_S]

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

[Cyclone_S]

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