Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 07 Mar 2002
Offline Last Active Yesterday, 03:44 PM

#5288968 Lagrange multiplier in constrained dynamics

Posted by Álvaro on 27 April 2016 - 01:28 PM

I read parts of the tutorial and I think that way of thinking of Lagrange multipliers is probably very useful. The part you quoted about minimizing C seems wrong, though.

#5288909 Lagrange multiplier in constrained dynamics

Posted by Álvaro on 27 April 2016 - 07:46 AM

I haven't clicked on the link to the tutorial, but I can explain how Lagrange multipliers work.

You want to minimize f(x,y) subject to g(x,y) = 0. We'll introduce an additional variable l (usually "lambda", but I don't have that letter available). Let's look at the function

L(x,y,l) = f(x,y) - l*g(x,y)

and imagine you've found a point where the derivative of L with respect to each of the three variables is 0. You then have

dL/dx = df/dx - l*dg/dx = 0
dL/dy = df/dy - l*dg/dx = 0
dL/dl = g(x,y) = 0

The last condition guarantees that the constraint is being satisfied. The other two basically say that the levels of f and g are tangent.

These are necessary conditions for a point (x,y) to be a solution to your problem. Sufficient conditions do exist, but they are a bit trickier to think about, and this may or may not be important in your case.

#5287745 Is there a named algorithm for this method of splitting a large triangle into...

Posted by Álvaro on 20 April 2016 - 04:50 AM

I don't know of a name, but here's a version I like better:
- For each side of the triangle, check if it's longer than some threshold.
- If all 3 sides are too long, divide the triangle into 4 triangles.
- If 2 sides are too long, divide the triangle into 3 triangles (there are 2 ways to do this).
- If 1 side is too long, divide the triangle into 2 triangles.

This has the huge advantage that the subdivision can be done independently in triangles of the same triangulation without introducing cracks.

Here's an even simpler version with the same feature:
- Pick the longest side.
- If it's longer than some threshold, divide the triangle into 2 triangles.

#5287540 What is more expensive in float?

Posted by Álvaro on 18 April 2016 - 03:39 PM

What are you guys doing where trigonometric functions are used so heavily as to make a difference in performance?

#5287164 Move piece with minimax algorithm

Posted by Álvaro on 16 April 2016 - 04:40 AM

Your undo logic is suspect in a couple of ways:

 * Why don't you have a function to undo moves, just like you have a function to make them?

 * Why don't you undo the move immediately after the recursive call to minimax?



Other pieces of advice:

 * Learn how to use a debugger!

 * Use the NegaMax variant so you don't have duplicated code for the min and the max part. Duplicated code is very hard to maintain. As you edit your code, there is a high probability that you'll introduce some asymmetry.

 * Separate the searching of the root to a different function, or your code will end up full of `if (depth == 0)' blocks. You already have 3 and you haven't even implemented iterative deepening, aspiration windows, time control... You are also using a global variable because you don't have a place to return the move, which should tell you that you are doing it wrong.


#5287094 My octagon is a circle and my pentagon is wonky :'(

Posted by Álvaro on 15 April 2016 - 02:27 PM

I am sorry I helped you figure out what was wrong with your code in that other thread. I really am, because although my help came with the warning "don't get used to it", you obviously got used to it.

You need to start debugging your own code and figuring out how to solve problems on your own. You are not going to get very far if we need to hold your hand every step of the way.

#5287090 My octagon is a circle and my pentagon is wonky :'(

Posted by Álvaro on 15 April 2016 - 01:47 PM

That looks like a perfectly good pentagon to me. If you are complaining that a 2-color display with a resolution of something like 20x20 isn't very good, I have to agree with you.

#5287074 My octagon is a circle and my pentagon is wonky :'(

Posted by Álvaro on 15 April 2016 - 12:51 PM

I have one word for you: loop.

#5287065 towards a faster A*

Posted by Álvaro on 15 April 2016 - 11:47 AM

The usual implementation uses a heap for the open list, which allows insertions and retrieval of the lowest f node in time O(log(number_of_open_nodes)). A node can be added to the list multiple times, which is fine as long as you check if the lowest-f open node is closed; in that case simply skip it.

I would start by implementing that. I would try the other stuff only if that's not fast enough.

Good luck!

#5286631 C++ Rotating 2D shape in list

Posted by Álvaro on 13 April 2016 - 05:08 AM

As you can see from the code above I use push back to add the rotated vertices to the list and then re draw the shape with the draw shape function with the newly defined vertices, what I mean by no output is I draw the shape, which display the shape, rotate the vertices using the rotate function, clear the console to re draw but when I re draw nothing appears like it cant find the newly defined vertices.

From a symptom like "nothing appears" you can't know if the problem is in the piece of code you posted or somewhere else. Use the debugger to step into the function and see what it does. You can also add a couple of lines of code to print some debugging output, for instance with the list of vertices just before returning from the function.

#5286561 C++ Rotating 2D shape in list

Posted by Álvaro on 12 April 2016 - 08:47 PM

Just for fun, here's how I would probably implement something like that:

#include <iostream>
#include <vector>
#include <complex>

typedef std::complex<float> C;

std::vector<C> rotate_points(std::vector<C> const &points, float angle, C center_of_rotation) {
  std::vector<C> result;
  C rotation = std::polar(1.0f, angle);
  for (auto point : points)
    result.emplace_back(center_of_rotation + (point - center_of_rotation) * rotation);
  return result;

const float TAU = std::atan(1.0f) * 8.0f;

int main() {
  std::vector<C> points = {C(1.0f, 1.0f), C(-2.0f, -1.0f)};
  float angle = TAU * 0.25f; // A quarter of a turn, a.k.a. 90 degrees
  std::vector<C> rotated_points = rotate_points(points, angle, C(1.0f, 1.0f));
  for (auto point : rotated_points)
    std::cout << point << '\n';

#5286558 C++ Rotating 2D shape in list

Posted by Álvaro on 12 April 2016 - 08:32 PM

Here, free code commentary. Don't get used to it, though; Nypyren is absolutely right that you should learn to go through the code yourself, either executing the code by hand or with the help of a debugger.

	int x, y, xx, yy; // Why are these variables here? I don't know what they mean. They should be declared where you use them, not here.
	double radians; // Same thing. At least this one has a better name. Although it's only the units...
	list<Vertex>::iterator itr = vertices.begin(); // One would normally put this line and the two marked with (*) in a single for loop.
	while (itr != vertices.end()) // (*)
		x = centroid.getX(); // This would be a good place to declare the type of x. But the value you are assigning never gets used.
		y = centroid.getY();

		x = vertices.back().getX() - centroid.getX(); // Oh, so this is what you wanted x to be.
		y = vertices.back().getY() - centroid.getY();

		radians = degrees * PI / 180; // If degrees doesn't change inside the loop, why is this computation inside the loop?
		xx = round(x * cos(radians) - y * sin(radians)); // And why are you using integer coordinates? Rotation wonn't work too well..
		yy = round(y * cos(radians) + x * sin(radians));
		xx = xx + centroid.getX(); // Here you are modifying xx, which means the variable meant something up to this point, and something different from now on.
		yy = yy + centroid.getY();
		vertices.push_back(Vertex(xx, yy));

		itr++; // (*) It's probably better to use ++itr, but you are not ready to understand why, so don't worry about it too much for now.


I now get no output to the console?

What output did you expect? I didn't see any line of code in what you posted that printed anything.

#5286277 C++ Rotating 2D shape in list

Posted by Álvaro on 11 April 2016 - 05:28 AM

// x = x * cos(degrees in radians) - y * sin(degrees in radians)
    // y = y * cos(degrees in radians) + x * sin(degrees in radians)

Instead, I would do this like so:

// x2 = x * cos(degrees in radians) - y * sin(degrees in radians)
    // y = y * cos(degrees in radians) + x * sin(degrees in radians)

.. So x won't change in the first line, since it's used in the second one too (you're going to need the original x, not the rotated one for y rotation) :)

There's a good habit I follow which is not to reuse variables. If the coordinates of the unrotated point are x and y, the coordinates of the rotated point should be something else, like x_rotated, y_rotated.

#5286192 Any good ideas on how to get the "ideal line" of a track?

Posted by Álvaro on 10 April 2016 - 03:16 PM

A dot-product trick? I was thinking of some dynamic programming and optimal control, but perhaps that's way more trouble than you are willing to go through.


A similar approach would be to train a neural network using DQN.

#5286033 C++ best way to break out of nested for loops

Posted by Álvaro on 09 April 2016 - 10:56 AM

I strongly disagree with the advice of using a boolean variable. It's a much worse way to express control flow than any of the alternatives. Moving the loop into a separate function should be done if it makes sense (you can give it a good name, it has a well-defined interface... that kind of thing), not because you are trying to avoid writing `goto' at all costs. That being said, it often does make sense to move the loop into a separate function.