• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
BurdenJohn

A list that does not disturb the order when pushed/popped?

21 posts in this topic

Currently developing a game in C++.

My server (in C++) holds a list of players that are connected.

 

Players in this list can be either pushed or popped off the list.

Each player has a unique ID that they hold throughout the game.

 

The id is actually their place in the list.

 

For example some pseudo code:
 

List<Player> players = new List();

players.add(new Player("Todd", players.getThisListPosition()));
players.add(new Player("Ricky", players.getThisListPosition()));
players.add(new Player("Bob", players.getThisListPosition()));
players.add(new Player("Tim", players.getThisListPosition()));
players.add(new Player("Anna", players.getThisListPosition()));

For each player, their position in the list is their id. (assuming players.getThisListPosition() sets their ID as their position in the list).

 

Assume that the players were added when they contacted the server.

The list looks like so:

 

players

[0] = Todd

[1] = Ricky

[2] = Bob

[3] = Tim

[4] = Anna

 

Assuming the values of the list are the player instances in memory.

 

Now lets say Ricky leaves, players.pop( getID(playerThatLeft() ) );

The list looks like this now:
[0] = Todd

[1] = null

[2] = Bob

[3] = Tim

[4] = Anna

 

^This is ideal. This is what I want. However in reality the list would look like this:

 

[0] = Todd

[1] = Bob

[2] = Tim

[3] = Anna

 

^This is not what I want.

 

I want to retain the players positions in the list as they originally were. I don't want the list order to be modified.

Is there anything in C++ that I can use that will do this?

 

2

Share this post


Link to post
Share on other sites

That sounds like a job for an array-like data structure. So I think a vector is suitable for this. When you remove the item, you mark that item's slot as unused.

2

Share this post


Link to post
Share on other sites

Well I'm off to an okay start.

Made a custom list class that uses a vector.

 

So far when I add players, their ids are fine.

When I remove a player, the players still retain their ids, which is fine, however after removing a player

and then adding a new player, the player does not fill the position of the one that was previously removed.

 

Example:

 

push_back josh, tod, bob, tim, steph, giorgio.

 

[0] Josh

[1] Tod

[2] Bob

[3] Tim

[4] Steph

[5] Giorgio

 

remove bob

List now prints:
 

[0] Josh

[1] Tod

[3] Tim

[4] Steph

[5] Giorgio

 

push_back Greg

 

List now prints:

[0] Josh

[1] Tod

[3] Tim

[4] Steph

[5] Giorgio

[5] Greg

 

The reason why 5 is repeated is because the id that is assigned to the player is based on the size of the list.

However I need it so the ID is based on the position that it fills, but currently the vector isn't filling the list, its just pushing

it to the back. Not sure how to fill empty slots (in this case, position 2 was supposed to be assigned to greg).

 

playerList.h

#include <vector>
#include "player.h"
#include <iostream>
#pragma once

class PlayerList{
	std::vector<Player> playList; //the list
public:
	void addPlayer(Player* p); //adds Player p
	void removePlayer(unsigned int id); //removes player given id
	Player getPlayer(unsigned int id); //gets player given id
	void printList();
};

playerList.cpp

#include "playerList.h"

void PlayerList::printList(){
	for(std::vector<Player>::iterator it = playList.begin(); it != playList.end(); ++it) {
		std::cout << "[" << it->id << "]     " << it->name << std::endl;
	}
}

void PlayerList::addPlayer(Player* p){
	//std::cout << "ADDING PLAYER, LIST SIZE: " << playList.size() << std::endl;
	unsigned int theId = playList.size();
	p->id = theId;
	playList.push_back(*p);
	std::cout << "ADDING PLAYER, theId: " << theId << std::endl;
}

void PlayerList::removePlayer(unsigned int id){
	for(std::vector<Player>::iterator it = playList.begin(); it != playList.end(); ++it) {
		if(it->id == id){
			playList.erase(it);
		}
	}
}

One thing I could do, is when adding a player, check the list for any blank spots that aren't filled, but how do I do this?

When I remove a player, how would I mark its position in the list as "blank" rather than just erase it completely?

Edited by BurdenJohn
0

Share this post


Link to post
Share on other sites

You should use ApochPiQ's suggestion of a vector of pointers. Removal of one in the middle becomes invalidating the pointer (whether unique_ptr's reset or a raw null). Adding a new one then requires traversing the array to see if any slots can be reassigned without push_back (which might reallocate and copy, but still better than copying an entire array of large objects).

 

std::vector::erase literally removes the element, copying everything else down a slot. To use a vector of objects like the pointer version, you'd need a way to mark a Player object as invalid so you can search for an available id in the middle of the list before using push_back to add to the end.

0

Share this post


Link to post
Share on other sites

Hmm not sure what's going on here, but now I'm trying to use std::unique_ptr but I'm getting a private member access error?

#include "playerList.h"

void PlayerList::printList(){
	std::cout << "PRINTING PLAYER LIST" << std::endl;
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		Player* p = it->get();
		std::cout << '[' << p->id << ']' << p->name <<  std::endl;
	}
}

void PlayerList::addPlayer(Player* p){
	std::cout << "ATTEMPTING TO ADD PLAYER: " << p->name << std::endl;
	std::unique_ptr<Player> uptr(p);

	unsigned int count = 0;
	unsigned int nullCount = 0;

	//Check for a null player, if we find one, replace it with the new one
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		count++;
		Player* ps = it->get();
		if(it->get() == nullptr){
			nullCount++;
			unsigned int pos = it - playList.begin();
			it->swap(uptr);
			it->get()->id = pos;
			return;
		}
	}
	//If we didn't find a null player 
	unsigned int pos = playList.size();
	uptr->id = pos;
	playList.push_back(uptr);
}

void PlayerList::removePlayer(unsigned int id){
	
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		Player* p = it->get();
		if(p->id == id){
			std::cout << "REMOVING PLAYER: " << p->name << std::endl;
			it->reset();
		}
	}
	
}

 

C2248: 'std::unique_ptr<_Ty>::unique_ptr' : cannot access private member declared in class 'std::unique_ptr<_Ty>'

 

The idea now is that when I add a player, I check for any null players that are in the list.

 

If I find one, I make swap the null player with the new player I'm adding, and the new player gets the id that's equal to the current position of the iteration

( it - playList.begin() )

 

 

A null player is now a player that, when it gets removed, its unique_ptr is reset().
 
Not sure if this works though, can't figure out why I'm getting that error. I've read that it has to do with making a copy? I don't recall ever making a copy of the unique_ptr?
Edited by BurdenJohn
0

Share this post


Link to post
Share on other sites
push_back() is probably the culprit, although if you want to know for sure, look at the line that is reporting the error.

Try emplace_back() instead; it will move the pointer instead of copying it.
0

Share this post


Link to post
Share on other sites

The thing is the error comes from File: "xmemory0" at line 617:

#define _ALLOC_MEMBER_CONSTRUCT( \
	TEMPLATE_LIST, PADDING_LIST, LIST, COMMA, CALL_OPT, X2, X3, X4) \
	template<class _Objty COMMA LIST(_CLASS_TYPE)> \
		void construct(_Objty *_Ptr COMMA LIST(_TYPE_REFREF_ARG)) \
		{	/* construct _Objty(_Types...) at _Ptr */ \
		::new ((void *)_Ptr) _Objty(LIST(_FORWARD_ARG)); \
		}

_VARIADIC_EXPAND_0X(_ALLOC_MEMBER_CONSTRUCT, , , , )
#undef _ALLOC_MEMBER_CONSTRUCT

Also, commenting out push_back() seemed to get the error away, but of course I still need that in (caused an exception).

So I tried your emplace_back() suggestion, and I get the same error as before (cannot access private member...) line 617 of file xmemory0 as posted above.

Here's my playerList.cpp code as it stands:

http://pastie.org/private/0lhdxjoczzjfdg2acyzq

 

Does it seem like my list would work though using these methods?

Edited by BurdenJohn
0

Share this post


Link to post
Share on other sites

Release the pointer at specific position when the player leaves and assign nullptr to it?

Edited by GuardianX
0

Share this post


Link to post
Share on other sites
Post the entire compile error, from the Output pane in Visual Studio, with the Debug filter selected from the dropdown. Your compiler is telling you exactly where the problem is, all the way from the "real" error up through the templates of the standard library implementation and into your own code; it can be hard to read, but learning to interpret these error chains is immensely valuable.

The last chunk of the error output should point you exactly to what part of your code is causing the issue.


[edit] Afterthought: you should emplace_back the raw pointer, not the unique_ptr. In fact you shouldn't need to create a unique_ptr inside the function at all. Edited by ApochPiQ
2

Share this post


Link to post
Share on other sites
List<Player> players = new List();

 

ah! Java/C# programmer in the room tongue.png That's no C++. 

 

Anyway.. to answer your question, you are trying to have a player ID being equal to his position in the list. This is basically, impossible, or possible but VERY error prone.

 

There are many ways to go around the problem, the one I use for my server stuff is to have the player ID as part of the Player data structure. My player list is a std::vector and then I have an helper function Player* getPlayerFromID(unsigned char id); that looks for a player with that ID in my list and returns it. A map might work better if you discover that your getPlayerFromID is a bottleneck.. personally it isn't so don't bother.

 

The other convoluted way would be to reassign IDs every time a player is added or removed to the list. The adding part is easy because it only involves the currently added player.. the removing is tricky because you'll have to notify all your clients "hey your player ID has changed".. which I think it's just a bad idea.

0

Share this post


Link to post
Share on other sites

Assuming you won't have more than 256 player online, you can use a plain old array, like Player *players[256].
Memset to zero and you'll have all players=NULL.
When a player connect, scan the array and look for the first NULL; when a player leave, delete players[id], and set players[id]=null

Honestly this was the simplest solution!

Just a quick question though, here's my removePlayer function:
 

int PlayerList::removePlayer(unsigned int id){
	//std::cout << "===REMOVING PLAYER===" << std::endl;
	if(players[id] != NULL){
		delete players[id];
		players[id] = NULL;
	}
	return 0;
}

It works when I remove the line "delete players[id];"

For some reason when I leave that in, I get an exception when I try to execute removePlayer(2) for example.

It says the heap gets corrupted.

 

Why is that? And also, why do I need to delete that piece of memory, because when I set it to NULL, the reference is gone anyways?

Or would the player instance still be in memory? If that's the case, how do I get around this issue where it corrupts the heap?

0

Share this post


Link to post
Share on other sites

You need to post more of your code if you want us to tell you why it's crashing. smile.png

 

Are you calling 'delete' on something you haven't called 'new' on?

Why are you using 'new' or 'delete' at all here? Even smart pointers here is probably unnecessary.

Your code probably shouldn't contain any occurrences of new or delete.

 

In C++, the 'new' keyword and the 'delete' keyword do things very differently from other languages you might have used, and need to be handled with care.

 

Why do you need to delete the memory of your players, anyway? Why not just mark them (with a bool) as not in use?

Why are your Player structs dynamically allocated instead of on the stack?

 

If you use C++11, which you are if you have access to std::unique_ptr, then you should use nullptr, not NULL. There is a reason for that.

 

I mentioned earlier, why does the order in memory of your players matter?

Why are you using a single variable (the ID) to handle more than one purpose (position in memory and identification)?

 

You definitely don't need a custom container. tongue.png

 

Here's my suggested solution: std::unordered_map<PlayerID, Player>

 

If you want to *remove* a player from memory (why?), call myMap.erase(playerID).

 

But if you want to preserve the prior existence of a player, just use a boolean to mark him as no longer active. wink.png

myMap.at(playerID).isActive = false;

For new IDs, just hold the last used ID and increment it. Don't let the current size of your containers dictate your IDs if you're going to be removing elements.

PlayerID newPlayerID = ++lastUsedPlayerID;
Edited by Servant of the Lord
0

Share this post


Link to post
Share on other sites
I don't understand this new trend against new and delete. In a simple scenario like this, there's no reason not to use new and delete, it's ABC of programming with c++. If you can't handle a simple array of pointers, you have no hope with c++. It's a good exercise for the OP and understanding why he gets an error when deleting a player will save him a lot of troubles in the future.

@burden: your remove fn is correct, the error probably is in your create function Edited by Giallanon
2

Share this post


Link to post
Share on other sites

Thank you all for the suggestions.

I'm going to go with Giallanon's suggestion, was very simple and it works!

 

Thanks guys.

0

Share this post


Link to post
Share on other sites

@servant: I voted up your answer, because I like the way you put it down, and also because I agree with everything you wrote.

 

But...

IMO, before using STL, or smart pointers or any "advanced" c++ things, a beginner should understand perfectly what is a (raw) pointer, how it's used, why they exists, what is a memory leak and why/how they are related to the use of pointers.

I think everyone should go trough the process of using pointers and discover that somewhere, sometimes, your program is leaking memory. You should fire up your debugger and go figure.

I think this is the only way to learn. When you understand the power of pointers, then you can choose a (may better) approach, like not using new at all for example.

So my complains against "this new trend" is more about the fear that the the new generation of programmers will grow up without understanding the raw power of c/c++. Why using c++ in first place if you don't have the time/will to learn the hard stuff. There are plenty of other languages that will deal with pointers in a transparent way (c# is a good example).

 

Anyway, in this specific case, I would have used a placement new, over a pre-allocated memory block of 256 * sizeof(Player), maybe with a little care about memory alignment.

The array of 256 pointer to player is still the best option IMO for a few reason:

1) given the player ID, you have O(1) access to the player data

2) search within the array for null pointers is very cache friendly since a single pointer is only 4 or 8 bytew, so the whole array is 1 or 2 KB of memory

3) from a psychologically point of view, calling new when a new player enter the game, and calling delete when he leave, is something that feels right to me

 

When a player come, you have to initialize a player class. If you use new Player(),  the constructor will take care of initialization; if you use an already existing instance of player, then you have to call some method like player[id].initialize() or player[id].whatever() just to setup the class.

I fell like new Player() is better.

The same goes for a player that log off, calling delete player[id] feels better to me than calling player[id].kill()

It's the same thing, just called with different names.

 

I agree that a std::vector of pointers is a non sense, that's why my solution involve a plain old array of pointers.

2

Share this post


Link to post
Share on other sites

Let's reserve the philosophical debate over learning style (which is endless and therefore pointless) for other threads, and keep this on the subject of the poster's problem, please.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0