Trying to get unique random entries from an array

Author

Message

bigtunacan

9

Years of Service

User Offline

Joined: 24th Jul 2015

Location:

Posted: 24th Jan 2017 00:19

Link

I'm trying to randomly grab tiles from an array of game pieces. I can't get the same piece twice and once a piece is used it can't be used again. Below is my code where I have attempted this.

Something is slightly wrong as two things happen periodically.

1) The first is that I still occasionally get a duplicate game piece

This bit of code was supposed to prevent this...

+ Code Snippet

found = 1
while found = 1
	piece = Random(0, game_pieces.length - 1)
	if index_array.find(piece) = -1
		found = 0
	endif
endwhile

2) The second issue is that occasionally I don't even get enough pieces for a hand... Now I would expect that to happen towards the end of the game as pieces run out, but this will happens even on the very first turn of the game when there are 100+ pieces remaining.

+ Code Snippet

function InitHand(game_pieces as GamePiece[])
	player_pieces as HeldGamePiece[HAND_COUNT]

	index_array as integer[HAND_COUNT]
	for ix = 0 to HAND_COUNT
		found = 1
		while found = 1
			piece = Random(0, game_pieces.length - 1)
			if index_array.find(piece) = -1
				found = 0
			endif
		endwhile
		index_array[ix] = piece
	next ix

	for ix = 0 to HAND_COUNT
		player_pieces[ix].piece = game_pieces[index_array[ix]]
		SetSpritePosition(player_pieces[ix].piece.largeSprite, (ix * (GetSpriteWidth(player_pieces[ix].piece.largeSprite) + 5)) + 10, 1105)
		player_pieces[ix].heldX = GetSpriteX(player_pieces[ix].piece.largeSprite)
		player_pieces[ix].heldY = GetSpriteY(player_pieces[ix].piece.largeSprite)
	next ix

	index_array.sort()
	index_array.reverse()

	for ix = 0 to (index_array.length - 1)
		game_pieces.remove(index_array[ix])
	next ix
	
endfunction player_pieces as HeldGamePiece[]

Back to top

Profile PM

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 24th Jan 2017 00:28 Edited at: 24th Jan 2017 00:29

Link

1.
you can use two random number of indexes and exchange booth, if you do this often its shuffled.
see integer = Random2( from, to ) and SetRandomSeed2 ( seed )

2.
you should use by reference here or you have a copy inside, i saw you using .remove there.
function InitHand(game_pieces ref as GamePiece[])

AGK (Steam) V2017.01.09 : Windows 10 Pro 64 Bit : AMD (16.12.1) Radeon R7 265 : Mac mini OS Sierra (10.12.2)

Back to top

Profile PM Email

easter bunny

12

Years of Service

User Offline

Joined: 20th Nov 2012

Playing: Dota 2

Posted: 24th Jan 2017 00:34 Edited at: 24th Jan 2017 00:37

Link

This is a fairly modular technique for choosing pieces from an array (untested). Not sure if it'll work with your code or if it's what you're looking for though.

+ Code Snippet

Type GamePieces
 used as integer
Endtype

global leng=100
global p as GamePieces[leng] //pretty sure you have to use a constant to init array len so this line will fail?

id=grabPiece() //you can use this function up to 100 times, after which it will start returning -1 meaning no more available pieces

function grabLotsOfPieces(count as integer)
 v=0

 for k=1 to count
  v=grabPiece() //simply add v to an array each iteration and return that array. If you run out of pieces then it will finish the loop there
  if v=-1 then k=count+1
 next
endfunction

function grabPiece() 
 pos = random(0,leng) //choose the starting position
 ret=-1
 for i=1 to leng//loop through all pieces and take the next available piece. Starting with the starting position
   k=i
   if k>100 then k=k-leng
   if p[k].used=0
    ret=k
    i=leng+1 //finish the loop now
    p[k].used=1 //set the piece to used so it wont be used ever again
   endif
 next
endfunction ret

Audacia Games - Latest WIP - AUTOMAYTE 2.1, AppGameKit one click deploy to Android
130,000 installs with AppGameKit and counting

Back to top

Profile PM Email

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 24th Jan 2017 00:58 Edited at: 24th Jan 2017 01:01

Link

Quote: "global p as GamePieces[leng] //pretty sure you have to use a constant to init array len so this line will fail?"

if you not want a constant this should work:
global leng=100
global p as GamePieces[0]
p.length = leng

u can also use exit to get out of for next.

AGK (Steam) V2017.01.09 : Windows 10 Pro 64 Bit : AMD (16.12.1) Radeon R7 265 : Mac mini OS Sierra (10.12.2)

Back to top

Profile PM Email

bigtunacan

9

Years of Service

User Offline

Joined: 24th Jul 2015

Location:

Posted: 24th Jan 2017 01:08

Link

Markus,

Good catch on the passing by value instead of reference.

I didn't follow your comment on the randomization?

Quote: "
1.
you can use two random number of indexes and exchange booth, if you do this often its shuffled.
see integer = Random2( from, to ) and SetRandomSeed2 ( seed )
"

My thought was that the way I have it setup it should get a random number, check if it is in the array already. If it finds it then it loops and gets a new random number. So I would have anticipated it getting stuck in an infinite loop if it kept only getting duplicates, but that isn't happening either so my logic is somehow not correctly detecting the duplicates?

Back to top

Profile PM

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 24th Jan 2017 02:42

Link

oh i had misread point 1.
i think if you remove the piece from batch array and add it into hand held array and vice versa its more simpler to get a random index of the batch.
each piece exist once in your game. i guess u are making a card game.

this part of your code is very confusing

Quote: "
index_array as integer[HAND_COUNT]
for ix = 0 to HAND_COUNT
found = 1
while found = 1
piece = Random(0, game_pieces.length - 1)
if index_array.find(piece) = -1
found = 0
endif
endwhile
index_array[ix] = piece
next ix
"

AGK (Steam) V2017.01.09 : Windows 10 Pro 64 Bit : AMD (16.12.1) Radeon R7 265 : Mac mini OS Sierra (10.12.2)

Back to top

Profile PM Email

bigtunacan

9

Years of Service

User Offline

Joined: 24th Jul 2015

Location:

Posted: 24th Jan 2017 03:23

Link

It is a game sort of similar to Words With Friends, but the idea is similar to a card game. There are a variety of 25 unique pieces and each game begins with a set number of each piece. The game ends when the players have either used all of the pieces or can no longer make any valid moves.

At the beginning of the game the player will get a random "hand of pieces", much like a player would a hand of cards. These are taken from the set of pieces and so are no longer available.

The current function I displayed originally would only be used to fill the hand on the very first time so their hand is empty; a separate function with some overlap in logic will be used to refill a hand that may not be empty.

+ Code Snippet


// Used as a temporary storage mechanism of the random indices to game pieces 
// that will be put in the players hand and removed from the set.
index_array as integer[HAND_COUNT]    

// Get 7 random pieces from the set
for ix = 0 to HAND_COUNT
        // Start each loop by assuming a duplicate random was generated
	found = 1

       // Loop until the random is not a duplicate
	while found = 1
                // Get a random piece
		piece = Random(0, game_pieces.length - 1)

                // Did we get a duplicate?
		if index_array.find(piece) = -1
                        // Nope, it shouldn't be a duplicate so break the while loop
			found = 0
		endif
	endwhile
        // Put the random piece into the temporary index_array
        // But, "Oh hai", it's not really unique and we got a duplicate
        //   or worse yet somehow I have less than 7 pieces, WTF?
        // Stab out my eyes...
	index_array[ix] = piece
next ix

Back to top

Profile PM

PSY

Developer

8

Years of Service

User Offline

Joined: 3rd Jul 2016

Location: Laniakea Supercluster

Posted: 24th Jan 2017 21:52

Link

You might want to have a look at this thread:
https://forum.thegamecreators.com/thread/218607#msg2594211

Cheers,
PSY

PSY LABS Games
Coders don't die, they just gosub without return

Back to top

Profile PM Website

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 25th Jan 2017 00:19

Link

why not use
index from game_pieces that not exists in player_pieces
add player_pieces here, game_pieces remove index

this index_array part seems needless for me.

i would use the game_pieces and player_pieces as reference argument for this function.

AGK (Steam) V2017.01.09 : Windows 10 Pro 64 Bit : AMD (16.12.1) Radeon R7 265 : Mac mini OS Sierra (10.12.2)

Back to top

Profile PM Email

bigtunacan

9

Years of Service

User Offline

Joined: 24th Jul 2015

Location:

Posted: 25th Jan 2017 02:05

Link

PSY,

Thanks; that's useful.

Markus,

What you are suggesting makes sense and seems cleaner right now. I feel like there is a reason I used the temporary array instead, but I can't recall what it was now and it was late so maybe it was just sleep deprivation

I am still confused why the particular version I have does not work; when I follow along with the logic it seems to me it should be fine. For now I will just take a pass at rewriting it since it shouldn't take too long.

Back to top

Profile PM

bigtunacan

9

Years of Service

User Offline

Joined: 24th Jul 2015

Location:

Posted: 25th Jan 2017 04:04 Edited at: 25th Jan 2017 04:08

Link

If you're interested; it is working now. This is the updated version based on Markus' feedback.

+ Code Snippet

function InitHand(game_pieces ref as GamePiece[], player_pieces ref as GamePiece[])
	pieces_remaining = game_pieces.length
	arr_len = player_pieces.length
	
	ix = player_pieces.length
	if player_pieces.length = -1 then ix = 0
	
	while ix <= HAND_COUNT
		found = 1
		piece = 0
		while found = 1
			piece = Random2(0, game_pieces.length - 1)
			if player_pieces.find(piece) = -1
				found = 0
			endif
		endwhile
		player_pieces.insert(game_pieces[piece])
		game_pieces.remove(piece)
		
		ix = ix + 1
	endwhile

	for ix = 0 to HAND_COUNT
		SetSpritePosition(player_pieces[ix].largeSprite, (ix * (GetSpriteWidth(player_pieces[ix].largeSprite) + 5)) + 10, 1105)
		player_pieces[ix].heldX = GetSpriteX(player_pieces[ix].largeSprite)
		player_pieces[ix].heldY = GetSpriteY(player_pieces[ix].largeSprite)
	next ix
endfunction

As I was reworking it I realized why I was using the temporary array. The two arrays that I'm moving between were different types. The player_pieces array used a type that contains a game piece type as one of it's attributes. I ended up changing it to use a single type that covered the needs of both.

Back to top

Profile PM

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 25th Jan 2017 14:12 Edited at: 25th Jan 2017 14:13

Link

in this InitHand you can reduce something. also be careful because this .find is your only exit condition. if this go wrong you have a endless loop.

found = 1
piece = 0
while found = 1
piece = Random2(0, game_pieces.length - 1)
if player_pieces.find(piece) = -1
found = 0
endif
endwhile

---------------------------------- to

do
piece = Random2(0, game_pieces.length - 1)
if player_pieces.find(piece) = -1 then exit
loop

------------------------------------

this while ix <= HAND_COUNT
i would replace with a for next 1 to HAND_COUNT-player_pieces.length

means you can have 8 cards maximal in hand but have only 4 in hand the for next is 1 to 4 and fill 4 new cards in.

less rows often result in better overview and understanding.

AGK (Steam) V2017.01.09 : Windows 10 Pro 64 Bit : AMD (16.12.1) Radeon R7 265 : Mac mini OS Sierra (10.12.2)

Back to top

Profile PM Email

Sorry your browser is not supported!

AppGameKit Classic Chat / Trying to get unique random entries from an array