Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Member Since 07 Mar 2002
Offline Last Active Yesterday, 08:33 PM

#5073219 Hashing connect -4 board (for Transposition table)..need some help :)

Posted by Álvaro on 27 June 2013 - 07:17 AM

Your advice is confusing. I shouldn't call anyone an authority but I should implicitly trust you based on the fact that I don't even know you?


No, you shouldn't trust me. You should only believe what I say because it's convincing. But I have a decent track record of getting things right. The reputation score in these forums is an imperfect indication of that. For people that have been around here long enough, they probably [hopefully] have had good experiences with my suggestions before. It's rather annoying that you would claim it can't be done with 49 bits when I think I just explained how it's done.


But let's get back to the technical details, which is what really matters.



Anyways, this is a place where we should be trying to clarify. I am still not understanding your approach. If we marked the highest bit with a single 1, we couldn't differentiate between each player. If you're feeling threatened/impatient perhaps you could just link to the original implementation? I tried googling around for it, briefly, but couldn't find it.


Perhaps Paradigm Shifter's explanation is clear to you. Just in case, I'll try to explain it in a different way.


Take a connect-4 position on a 7x6 board, with white and black pieces. Extend the board to be a 7x7 board by adding an extra row at the top. Now drop a blue piece on top of each column as a marker of how filled the column is. I claim that the set of squares occupied by either a white or a blue piece completely describes the position.


If you are given the set of squares described above, you can deduce that a square was occupied by a piece originally if and only if it is below some square in the set. If one of those squares is in the set itself, it must have contained a white piece; otherwise, it must have contained a black piece.


I should mention that one should be careful when using this value to compute indices into a hash table. If the hash table has a size that is a power of 2, only the low bits of the key will be used to determine where in the table to store the position. With this particular hash, the content of the leftmost columns completely determines the low bits, so there would be tons of collisions and the performance of the hash table would suffer. There are a couple of ways to solve this problem:

  1. Use a table whose size is not a power of 2. Some people like to use a prime number for this, although what really matters is that you pick a number N such that all the powers of 2 are different modulo N. For instance, Mersenne primes are bad choices.
  2. Do some bit-mixing on the key, like adding some constant, multiplying by some odd constant and flipping the top and bottom 32 bits. Notice that all those operations are invertible, so the key is still unique.

I recommend going with 2.

#5073028 catmull-rom length

Posted by Álvaro on 26 June 2013 - 12:39 PM

The math formula for the length of a cubic is an integral that doesn't seem to be expressible in terms of common functions (at least Mathematica and I don't know how to do it), so you need a numerical method anyway. If your sum of distances is precise enough and fast enough for your purpose, just go with it, because it is simple.

#5072946 Hashing connect -4 board (for Transposition table)..need some help :)

Posted by Álvaro on 26 June 2013 - 07:14 AM

John Tromp taught me of a slight variation of what hovermonkey suggests: Reserve an extra bit per column and encode a position by marking the first empty spot in each column and each white disk. That will give you a 49-bit unique encoding of the position.


EDIT: Here's what the code would look like (in C++, because I don't know Java):

Square numbering:
 6  13  20  27  34  41  48  <-- extra row to mark the first empty spot, even when the column is full
 5  12  19  26  33  40  47
 4  11  18  25  32  39  46
 3  10  17  24  31  38  45
 2   9  16  23  30  37  44
 1   8  15  22  29  36  43
 0   7  14  21  28  35  42
typedef unsigned long long u64;

u64 const BOTTOM_ROW = (1ull<<0) | (1ull<<7) | (1ull<<14) | (1ull<<21) | (1ull<<28) | (1ull<<35) | (1ull<<42);

struct Position {
  u64 white;
  u64 black;
  int move_number;

u64 encode(Position const &p) {
  u64 occupied = p.white | p.black;
  return ((occupied << 1) | BOTTOM_ROW) ^ p.black;

FURTHER EDIT: Sorry I had to fix my sloppy code.

#5072639 C++ Games?

Posted by Álvaro on 24 June 2013 - 10:38 PM

I just searched the web for Java games from 1998 and I found this video. For comparison, 1998 is the year StarCraft was released.


The performance gap between managed languages and compiled languages has probably been reduced somewhat, but it's still there. Indies can get away with programming in Java because their games don't need to squeeze all the performance the computer has to give. Actually, they can underutilize the hardware's potential by an order of magnitude and still be fun to play. Programming in Java allows them to be sloppy about details they don't care about (like establishing ownership and cleaning up dynamically allocated memory) and I've heard there are lots of things implemented in libraries, so they can program at a high level.


I have been using C or C++ for 20 years and I feel pretty productive in these languages, but I understand if some [even most] people are more productive when working in higher-level languages. If you want to make indie games, you should probably use whichever language you are most familiar with.

#5072588 Creating a game - what skills would I need to recruit?

Posted by Álvaro on 24 June 2013 - 03:51 PM

My tip is hire young people.20-25 years old


I just want to point out that age discrimination in hiring practices is illegal in the US. Just saying.

#5072561 Help with a 2D Space Shooter!

Posted by Álvaro on 24 June 2013 - 01:51 PM

The first thing is implementing the shooting, I mean, the bullets will go at the mouse direction, how can I implement the angles of shooting?


Don't use angles: Compute the vector from the shooter to the mouse and normalize it (i.e. divide it by its length). Then advance the position of the bullet by adding that vector multiplied by the bullet's speed.

The second is, how to implement a simply mini-map? Just showing where my ship is, some bases, etc...


This sounds fairly straight forward. You need to be more specific about what problem you are having.

#5072484 Extract corners of projection matrix...

Posted by Álvaro on 24 June 2013 - 07:04 AM

Yes, if you transform the unit cube by (Mview*Mprojection)-1,you'll get the frustum corners in world space. (for row major matrices, (Mprojection*Mview)-1 otherwise)

That's not quite right: "Row major" and "column major" refer to ways of representing matrices in memory. They have little to do with whether you represent vectors as columns or rows, which is what makes a difference in this case.
Perhaps someone that knows the conventions used in the video-game industry could suggest a better way to describe "representing columns as vectors".


EDIT: I found this relevant link.

#5072392 loop counters as class members? (memory usage)

Posted by Álvaro on 23 June 2013 - 10:37 PM

The fact that these variables were not local variables to begin with smells of premature [and misguided] optimization. Give variables as small a scope as possible, unless you find really strong reasons not to.

#5071982 Name of a particular property

Posted by Álvaro on 22 June 2013 - 04:43 AM

I don't know of a name, but I can make one up: "concatenation invariant". :)

#5071487 Using nonvirtual inheritance for informal 'interfaces'?

Posted by Álvaro on 20 June 2013 - 10:00 AM

Oooohhh! Aaaahhhh!


Now I just have to convince my company to ditch g++. :)

#5071417 Using nonvirtual inheritance for informal 'interfaces'?

Posted by Álvaro on 20 June 2013 - 06:06 AM

All the template magic in the world, and it still doesn't tell you anything more than you would know if you tried to call the function in the first place.


Oh, but the obscure error message you would get with the method you posted is much more fun to track down. :)

#5071295 Efficiency question

Posted by Álvaro on 19 June 2013 - 07:11 PM

What are the industry standards of "clean code"?


I used to work in the production group for a round-the-world trading operation, and a colleague used to say that code was clean enough when you are woken up in the middle of the night because of a problem, you can find the problem quickly, fix it, and not remember anything the next morning. :)

#5071193 html 5 canvas implementation

Posted by Álvaro on 19 June 2013 - 12:45 PM

That was just an example of what I found. But it looks like you'll have to write your own drawing primitives to get what you want. The results might be too slow, of course...

#5071146 html 5 canvas implementation

Posted by Álvaro on 19 June 2013 - 09:24 AM

Did you search the web? I found relevant links like this one in like 10 seconds...

#5070664 Prevent instantiation of base class with no pure virtual methods

Posted by Álvaro on 17 June 2013 - 08:23 PM

If you are going to inherit from Component, it should have a virtual destructor. Can you add "=0" to the destructor, and then define it to be empty anyway.


EDIT: Clicky.