Algorithms

Re: Best fit polynomial curve to non-continuous data points

23-May-11 6:02

Hmm, didn't think of the sensitivity thing... Giving that a shot now.

FWIW: with more-or-less random data, you'll never find a good fit with a single polynomial. What one normally does is a local approximation, which applies in a small region only. That is similar to a font being drawn as a sequence of Bezier curves; it pays of to have several simple Bezier curves, rather than trying to have a single very complex one (which in general will not be good enough).

It's not actually random data... It's graphing related values, so it should roughly cluster around y=x unless there's another factor (Which is what I'm trying to illustrate).

Proud to have finally moved to the A-Ark. Which one are you in?
Author of the Guardians Saga (Sci-Fi/Fantasy novels)

Luc Pattyn23-May-11 6:12

Re: Best fit polynomial curve to non-continuous data points

23-May-11 6:12

If you suspect some periodicity, I'd suggest you first subtract x, so according to what you said the average becomes zero, and the first-order approximation would be the x-axis itself. Then consider a Fourier analysis.

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.

Ian Shlasko23-May-11 7:28

Re: Best fit polynomial curve to non-continuous data points

23-May-11 7:28

Not a cyclic function, really... Bond valuations are a bit odd, so hard to explain... But dropping it to the X-axis does kinda help the initial approximation.

Still needs a lot more work (Got it to approximate the first degree, and working on expanding from there), but the sensitivity thing is working like a charm. Thanks Smile | :)

Proud to have finally moved to the A-Ark. <a href="http://en.wikipedia.org/wiki/Places_in_The_Hitchhiker%27s_Guide_to_the_Galaxy#Golgafrincham">Which one are you in?</a> Author of the <a href="http://www.serpentooth.com">Guardians Saga</a> (Sci-Fi/Fantasy novels)

Luc Pattyn23-May-11 7:50

Re: Best fit polynomial curve to non-continuous data points

23-May-11 7:50

you're welcome.

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.

Graham Toal23-May-11 9:54

Graham Toal

23-May-11 9:54

Assuming that standard numerical methods such as simplex aren't going to work here, and given that you do alreaduy have a fitness function available and a few coefficients to tweak, I'm wondering if perhaps a genetic algorithm or something like simulated annealing would work here?

Re: Best fit polynomial curve to non-continuous data points

Ian Shlasko23-May-11 9:58

Re: Best fit polynomial curve to non-continuous data points

23-May-11 9:58

Thanks for the input, guys... Got me thinking along the right lines, and that got me to the right google search...

I was searching for things like "curve fitting" and "best fit algorithm"... Turned out the 'proper' term was "Linear Regression"... And that got me here:

An Algorithm for Weighted Linear Regression[^]

Figures, the solution would be right here on CP Smile | :)

Proud to have finally moved to the A-Ark. Which one are you in?
Author of the Guardians Saga (Sci-Fi/Fantasy novels)

Alan Balkany24-May-11 3:25

Alan Balkany

24-May-11 3:25

I'm surprised with all those answers, no one gave you the right approach: Polynomial Regression: http://en.wikipedia.org/wiki/Polynomial_regression[^]

It will give you a best-fit quadratic or cubic equation (or even higher orders if you want). The Wikipedia link defines it, but the explanation there isn't very intuitive. The basic idea is you get an equation for the error terms, take the derivative, and set it to zero. Solving that gives you the equation with the minimum error.

Re: Best fit polynomial curve to non-continuous data points

Ian Shlasko24-May-11 3:41

Re: Best fit polynomial curve to non-continuous data points

24-May-11 3:41

Well, to be fair, the answers got me thinking along the right lines, and led me to the right terms, which brought me right back one of Walt's articles on CP... See my above post Smile | :)

Marked the original as solved

Proud to have finally moved to the A-Ark. Which one are you in?
Author of the Guardians Saga (Sci-Fi/Fantasy novels)

Alan Balkany24-May-11 3:43

Alan Balkany

24-May-11 3:43

But if your data set naturally has a curve, a linear model will be inaccurate.

Re: Best fit polynomial curve to non-continuous data points

Ian Shlasko24-May-11 3:46

Shortes pass find + walls bypassing

24-May-11 3:46

Well it's multiple linear regression... It lets me specify the degree.

Using Walt's library, it's looking perfect... Using third-degree (x^3, so a possible S-shape in the curve), and releasing the update next week.

Proud to have finally moved to the A-Ark. Which one are you in?
Author of the Guardians Saga (Sci-Fi/Fantasy novels)

alikalik14-May-11 22:22

alikalik

14-May-11 22:22

Hello,
I have an image and I mush find the shortest ways to connects points, and walls must be bypassed.
http://imageshack.us/photo/my-images/863/exampley.png

Can you recommend algorithm(s), that will help to make this program?

Re: Shortes pass find + walls bypassing

Luc Pattyn15-May-11 2:43

Re: Shortes pass find + walls bypassing

15-May-11 2:43

I suggest you start here[^].

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.

dasblinkenlight15-May-11 23:11

dasblinkenlight

15-May-11 23:11

Look up the maze routing algorithm - it may work for what you're trying to do. Here is an applet[^] that shows you the basic steps of the search (the forward "wave" and the backtracking).

Ackerman non-recursive function

Raminnamiranian4-May-11 22:31

Raminnamiranian

4-May-11 22:31

This is the code of Ackermann Algorithm.

Private Function T(ByVal m As Double, ByVal n As Double) As Double
Dim s1 As New Stack
Dim s2 As New Stack
s1.Clear()
s2.Clear()
If m = 0 Then
GoTo point
Else
Back: While n<>0
s1.Push(m – 1)
n = n - 1
End While
m = m - 1
n = 1
GoTo Point
point: Select Case (m)
Case 0
If s1.Count = 0 Then
Return n + 1
Else
s2.Push(n + 1)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 1
If s1.Count = 0 Then
Return n + 2
Else
s2.Push(n + 2)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 2
If s1.Count = 0 Then
Return (2 * n) + 3
Else
s2.Push((2 * n) + 3)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 3
If s1.Count = 0 Then
Return 5 + (8 * ((2 ^ n) – 1))
Else
s2.Push(5 + (8 * ((2 ^ n) – 1)))
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case Else
GoTo Back
End Select
End If
End Function

Re: Ackerman non-recursive function

Ravi Sant5-May-11 0:31

Ravi Sant

5-May-11 0:31

Thanks for Sharing. Now where do we use it? D'Oh! | :doh:

♫ 99 little bugs in the code,
99 bugs in the code
We fix a bug, compile it again
101 little bugs in the code ♫

Re: Ackerman non-recursive function

Luc Pattyn5-May-11 1:48

Re: Ackerman non-recursive function

5-May-11 1:48

this is not something I'm going to read as the code is not formatted. What happened to indentation?

Dead | X|

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.

Richard MacCutchan5-May-11 4:18

Richard MacCutchan

5-May-11 4:18

Is this a question? If so it is missing something. If it is supposed to be a Tip or Trick then please format it correctly, add some commentary about what it is and how it could be used, and post it in the proper place - you've been a member of CodeProject long enough to know where that is.

The best things in life are not things.

Search Algorithm

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;}
				}
				}
			}

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?

Cyclone_S16-Apr-11 13:10

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.

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.

Cyclone_S20-Apr-11 9:58

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;}
				
			}

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.

Cyclone_S21-Apr-11 14:45

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.

Cyclone_S22-Apr-11 9:57