Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 07 Mar 2002
Online Last Active Today, 03:59 AM

#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?

#5287470 towards a faster A*

Posted by Álvaro on 18 April 2016 - 09:03 AM

my choice of  a grid for the open and closed lists was inspired by Amit's A* pages where he combines the two lists onto one.
he goes into a fair amount of detail re: possible implementations, with lots of big O notation. but also points out that different algos are superior, depending on the value of N. specifically, he mentions the o log n algos and their poor performance with N < 200,000.

I have used a priority queue to compute the distance to goal in the game of Quoridor, which has a 9x9 board. The code is very simple and it was pretty fast: The alpha-beta search went through 1 to 2 million nodes per second --depending on the stage of the game-- while calling A* twice per leaf.

#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.

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

Posted by Álvaro on 09 April 2016 - 08:36 AM

There is precisely nothing wrong with using a goto here, so use a goto.


People should be taught that the way you break out of a loop is with a goto to the line after the loop, and you can skip to the next iteration of the loop with a goto to the last line of the loop block. These usages of goto are so common that the C language introduced special names for them: `break' and `continue'. Since they didn't introduce a special name for the goto that breaks out of nested loops, you still need to write a goto and a label, but what's going on is exactly the same thing.

#5285375 Stage 2, learning game programming C++.

Posted by Álvaro on 05 April 2016 - 08:18 PM

I would install SFML and go through the tutorials in the official website. Then it's time to make some games. You have probably read enough books and need to get some practice.