|
Hi Ian,
I don't think there are any closed formula's for what you are trying. What I would recommend is this, inspired by Newton-Raphson:
1. have some values a1,b1,c1,d1 and the corresponding value of your error function e1.
2. slightly change a1 (say by 1%) and recalculate e; find the "a-sensitivity" as (change in e)/(change in a)
3. same for b1, then c1, then d1
4. now choose new values a2,b2,c2,d2 based on the four sensitivities, maybe like so: a2=a1+coef*e/"a-sensitivity" where maybe coef is one.
then iterate until convergence is reached (i.e. sufficiently accurate); warning: this might diverge right away, if so try smaller values of coef (you could halve it in each consecutive try).
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).
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.
|
|
|
|
|
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)
|
|
|
|
|
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.
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.
|
|
|
|
|
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
<small><i>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></i><br>Author of the <a href="http://www.serpentooth.com">Guardians Saga</a> (Sci-Fi/Fantasy novels)</br></small>
|
|
|
|
|
you're welcome.
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.
|
|
|
|
|
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?
|
|
|
|
|
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
|
|
|
|
|
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.
|
|
|
|
|
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
Marked the original as solved
|
|
|
|
|
But if your data set naturally has a curve, a linear model will be inaccurate.
|
|
|
|
|
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.
|
|
|
|
|
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?
|
|
|
|
|
I suggest you start here[^].
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.
|
|
|
|
|
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).
|
|
|
|
|
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
|
|
|
|
|
Thanks for Sharing. Now where do we use it? 
♫ 99 little bugs in the code,
99 bugs in the code
We fix a bug, compile it again
101 little bugs in the code ♫
|
|
|
|
|
this is not something I'm going to read as the code is not formatted. What happened to indentation?
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.
|
|
|
|
|
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.
|
|
|
|
|
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;}
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;}
}
}
}
|
|
|
|
|
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;
}
}
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?
|
|
|
|
|
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.
|
|
|
|
|
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) {
direction_comp = UP;
return;
}
if (panel is higher than food) {
direction_comp = DOWN;
return;
}
if (panel is left of food) {
direction_comp = RIGHT;
return;
}
if (panel is right of food) {
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.
|
|
|
|
|
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()
{
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;}
}
if(direction_comp==1)
{
for(int I=0;I<(size_comp-1);I++)
{
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++)
{
if(head_comp2->Bottom == segments_comp[I]->panel->Top && head_comp2->Left == segments_comp[I]->panel->Left)
{direction_comp = 2;break;}
else if(head_comp2->Top == segments_comp[I]->panel->Bottom && head_comp2->Left == segments_comp[I]->panel->Left)
{direction_comp = -2;break;}
else {direction_comp = 2;}
}
}
}
}
else if(direction_comp==-1)
{
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)
{
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)
{direction_comp = -2;break;}
else if(head_comp2->Bottom == segments_comp[I]->panel->Top && head_comp2->Left == segments_comp[I]->panel->Left)
{direction_comp = 2;break;}
else{direction_comp =2;}
}
}
}
}
else if(direction_comp==2)
{
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)
{
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)
{direction_comp = 1;break;}
else if(head_comp2->Left == segments_comp[I]->panel->Right && head_comp2->Top == segments_comp[I]->panel->Top)
{direction_comp = -1;break;}
else{direction_comp = -1;}
}
}
}
}
else if(direction_comp==-2)
{
for(int I=0;I<(size_comp-1);I++)
{
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++)
{
if(head_comp2->Right == segments_comp[I]->panel->Left && head_comp2->Top == segments_comp[I]->panel->Top)
{direction_comp =1;break;}
else if(head_comp2->Left == segments_comp[I]->panel->Right && head_comp2->Top == segments_comp[I]->panel->Top)
{direction_comp =-1;break;}
else {direction_comp =1;}
}
}
}
}
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;}
}
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
