HexScape

[Xorlof]

My Google-fu wasn't up to finding such an algorithm. Where did you ever find it? Anyway, yes I came up with that exact method except:

1. I use the better route of XORing the values in step 2 (requiring all peers always generate a full 32 or 64-bit random value) instead of trying to put them in a specific order and hashing and,
2. if the RNG output was short, like 32-bits, I also salted the hash, first using a random value, later using the result of the previous hash.

I also came up with another method that is quite similar to the first one:

1. Have each peer generate a random seed for a RNG. (64-bit MWC is fast with a long enough period).
2. At the beginning of the game, each peer commits to their SEED without revealing it. They do this by hashing the seed (along with some salt if you want extra security). Peers wait for all other peers to commit before proceeding.
3. Every time a die roll is needed, each peer sends the next number generated by the local RNG (with its hidden seed/state) to all other peers. When all of the peers have reported their numbers, the final number used to determine the die roll is computed by XORing all of the values.
4. At the end of the game, all peers reveal what their seed (and salt if appropriate) was to all of the peers. The peers can then confirm 1) it matches the original commit hash, and 2) the sequence of pseudo-random values reported by a given peer throughout the game was indeed generated by the pseudo-RNG starting from their up-to-this-point secret seed.

The main advantage of this second method is that peers only have to only report once, not twice for every die roll, since they only have to commit to a secret value once per GAME, not once every ROLL. This speed increase wouldn't be very noticeable unless there was a large network latency between peers. The big disadvantage of this alternative is that shenanigans couldn't be discovered until the end of the game. A middle ground would be to require all peers to reveal every 5 minutes or so and reseed.

I also created a 3rd method using the same sort of "commit then reveal" pattern. This method is computationally super-fast and doesn't require any hashes, but would require a bit more work on the implementor's part (since he/she couldn't just call the ready-made cryptographic hash function.) It would also require a bit more work to explain here, but the math really isn't all that difficult. If generating a general purpose library for others to use, it's what I'd implement, but given how fast computers are, just reporting a hash output is plenty fast enough for a one-off project!

[Lyrgard]

At least, after gruesome amount of changes to the code, HexScape is working again, but this time with a new super flexible architecture, and quite more ready for multiplayer !

Back to working on the network code, it is ! With this new architecture, I'm confident I can have something up and runing in 2-3 weeks ! There probably still will be some bugs, but I'm sure a lot of people will be happy to test it ! (And now that I anounced that, I have no choice but to work hard, right ? )


@Xorlof

I typed "peer to peer dice roll" on google then followed some links to find http://gamedev.stackexchange.com/que...ted-3rd-party/
This links contains quite some ideas on the subject.
Google-fu is one of my forte !

as you said, I didn't searched for best efficienty, the computer now a day being what they are, but I'm impressed to see how far you thought about it.

I find your second solution to be worse than the first, except perhaps in extreme cases where network resource (or lack of) is the main problem, because you would have to adress a lot new problems (amongst them the player that suddently lost its connection before sending its seed for confirmation, or just manage the resending every 5 minutes for instance...), for little gain. It depends of course how many time per minutes the game need to roll dice.

I would like to read your third solution, if you have the time to write it down (perhaps by pm, I don't know it that stuff interest others 'scapers), just by plain curiosity ^_^

I like your idea to use XOR instead of ordering the seeds ! So simple and effective ! :

[UtahScott]

Really looking forward to this.

[Xorlof]

Those not interested in the techie stuff Lyrgard and I have been discussing, skip the spoiler. Really. It's something we could do via PM, but doing it in public lets others point out anything we've missed.

Spoiler Alert!

Lyrgard--In my defense, that page didn't exist when I last searched for such things 2 years ago. I did do some more searching last night and quickly discovered that what we've been discussing is called "bit commitment" protocols in cryptography. Searches for THAT include lots of algorithms, including what I came up with for method 3.

Your criticism of my method #2 is spot-on. It would be best used where network latency is an issue, such as more real time games. However, I just thought of a way to reduce the latency of method #1 down to basically the same as method #2:

1) Each peer commits to (for example) 128-bits at the start of the game by sending the hash of it.
2) When dice need to be rolled, all peers reveal their 128-bits. In the same packet, commit to a new set of 128 bits to be used whenever the next dice roll is needed. Check that the revealed bits match what was committed to in step 1 or a previous round of step 2, XOR them together, and use the output 128 bits to determine the dice rolls needed (e.g., 1d20, or 6d6).
3) If any peer ever drops and loses the previous values that it committed to, it reconnects and commits to a new 128-bits. If the drop occurred after any other peers had already revealed their 128-bits (i.e., in the middle of a dice roll), all peers re-commit, and then re-reveal. (And flag the dropped peer as doing something suspicious).

Additional safety could be added by making the committed bits able to be calculated in a non-parallelizable way that requires quite a bit of time (e.g., hours). The no committed bits would ever *have* to be lost. I haven't thought through how to do this. It seems feasible, but is probably more interesting as a brain exercise than a necessary feature.

[A3n]

I would've preferred somebody take it web-based, but I will accept any work done in this space as a triumph.

[Lyrgard]

@Xorlof : thanks for the details on your third solution. I especially like the reusing of a packet to send the next commitement !

@A3n : halas, webGL is not mature enough for now, I think, to start a web based 3D game. Sure there are impressive demo out there, but it is not widely enough supported the same way on every browser.


@All : I was quiet those last few days, but don't worry, HexScape is still under developement. I have stabilized the architecture, and coded the connection to the server, joining the main room, chating there and disconnection detection.
I'm currently coding the creation of a multiplayer game.

[Lyrgard]

HexScape is still alive !

Some news :

Player are now able to create game in a room, and it update the list of game that all player in the roo see. Another player can join a game, and the game can be started (the map is sent over the network, so only the creator of the game need to have the VirtualScape file).
Once in the game, players can chat and roll dice (rolled on the server).

I basically need to add the sharing of army and markers on cards when one player load his/her army / put markers, and the synchronisation of figure's moves on the map, and it should be usable.

I also have some refining to do for border cases, like leaving a game, or when a player disconnect. I also need to make sure that the connection stay alive, even if player take time thinking.


On the 3d figure models, I made some progress by making a custom light tent.

some photos :



It is basicaly a cardboard box that I cuted. 3 sides are covered by white cloth.

Even with a small lamp, the result is great !

Here are some photo of Concan and Drake, out of the light tent, with my small lamp:



The sames figures, the same lamp, just in the light tent this time :



To have better results, I should use two lamps, one on each side, but the result is already vastly better ! (also, the light tent is not finished yet, I still need the white background sheet)

[El T]

That's a sweet light tent! Glad to see you're making progress, great work so far.

[awesomeunleashed]

Pretty awesome stuff, Lyrgard. Can't wait until it's progressed enough that we can replace the current system with it.

[Crixus33]

Wow this looks cool. Any idea what will be needed to run the program? Nice progress Lyrgard.

[A3n]

Nice to see you still plodding along.

[Lyrgard]

Originally Posted by awesomeunleashed

Pretty awesome stuff, Lyrgard. Can't wait until it's progressed enough that we can replace the current system with it.

That's what I hope ! I hope I'll make it good enough to replace the current system and provide every one a mean to play online in 3D.

Originally Posted by Crixus33

Wow this looks cool. Any idea what will be needed to run the program? Nice progress Lyrgard.

I totally don't have any idea ! It runs on my computer, an old computer with only the graphic chipset integrated in the motherboard. I can display maps without problem at 60 fps. I also run two clients at the same time to test multiplayer. However, this rate drops when I add figures. I guess that any decent computer with a graphic card won't have any problem. Also, it is my first time making a 3D game, so their should be some way to make it lighter. We'll see what testers will report when it'll enter test phase !


Today, I was able to have two client running. One created the game, the other joined it, and the game was started. Each player could then load his army, and each was displayed on both side. Players was able to place figure on the board, and the figure are displayed on both side.
Now to add moving/removing figure over network support, and the markers, and it'll be very close to enter test phase.



Lastly, I'll probably need some help with the design, to help me make HexScape nicer to the eyes.
For instance, the home screen player see when the launch HexScape is that for now :

As you see, it's pretty bare... I would love a HexScape logo and icon, and for the home screen, I would gladly replace the button with two big clickable images, one representing solo mode, the other multiplayer.
So if you want to have your art in HexScape, feels free to give it a go !
Just one important point : for copyright reason, I made HexScape as a way to play generic hex-based board game, so no references to Heroscape should be on the art. The use of Hex shapes on the other hand is of course no problem.