c++ how to pick random items from a linked list

Question

I'm experimenting with a game program. I'm trying to have an random number of items generate. The code will produce the same item multiple times. I can get away with setting up a series of switch statements that will produce multiple search areas for a player to look through, thus getting a single new random item per area, but I'd like to learn how to deal with what I'm doing wrong here. Nothing helps one learn like an error.

I'm using a struct, a linked list, a class and pointers.

//genItem.h
#pragma once

struct item
{
    char itemName[50];
    int itemDamage;
    int itemStability;
    item* Next;
};

class genItem
{
public:
    genItem(void);
    ~genItem(void);
    int count();
    int add_item(item* currentItem);
    void generate_item(int d2, int s2);
    item *Head;
    item *Retrieve(int pos);
private:
    int size;
    int damage;
    int stability;
};

//genItem.cpp
#include <iostream>
#include "genItem.h"
#include <stdio.h> // NEED THIS FOR NULL TO WORK
#include <ctime>
using namespace std;

genItem::genItem(void)
    :size(0), Head(NULL)
{
}


genItem::~genItem(void)
{

}

int genItem::count()
{
    return size;
}

int genItem::add_item(item *thisItem)
{
    item *itemObject = new item;
    itemObject = thisItem;
    itemObject -> Next = Head;
    Head = itemObject;
    return size++;
}

item *genItem::Retrieve(int position)
{
    item *current = Head;
    for (int i = count() -1; i > position && current != NULL; i--)
    {
        current = current -> Next;
    }
    return current;
}

void genItem::generate_item(int d2, int s2)
{
    genItem *listItems = new genItem();
    item *listItem;

    srand (time(0));    

    int rn = 0;
    int total_in_cat = 10;
    int cat_item = 0;
    int rand_dam = rand();
    int rand_sta = rand();
    int per = rand();
    int base_d2 = 10;
    int base_s2 = 10;
    int rand_dam2 = rand();
    int rand_sta2 = rand();

    cat_item = per % total_in_cat;
    d2 = (rand_dam2 % base_d2) +2;
    s2 = (rand_sta2 % base_s2) + 2;

        if (rn == 0) // mushrooms
        {
            if(cat_item == 0)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "an earthball mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 1)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a devil's bolete mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 2)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a rotting jack o'lantern mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 3)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a fly agaric mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 4)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a poison pie mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 5)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a mature deathcap mushroom");
                listItem -> itemDamage = 50;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 6)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a shaggy inkcap mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 7)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a bleeding milkcap mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 8)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a velvet shank mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 9)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a destroying angel mushroom");
                listItem -> itemDamage = 100;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
        } //end group 0

    damage = d2;
    stability = s2;

    int j = rand();
    for (int j =0; j <= 3; j++)
    {
        cout << "\tJ equals: " << j << endl;
    for (int i =0; i < listItems -> count(); i++)
        {   
            item *found = listItems -> Retrieve(i);
            cout << "\tYou have found " << found -> itemName << "." << endl;
            cout << "\tIt has a damage rating of " << found -> itemDamage;
            cout << " and a stability rating of " << found -> itemStability << "."<< endl;
            cout << endl;
        }
    }
}

//main.cpp
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <ctime>
#include "genItem.h"

using namespace std;

int main()
{   
genItem *findItem = new genItem;

int d2 = 0;
int s2 = 0;

findItem ->generate_item(d2, s2);

cout << "\t"; system("pause");
return 0;
}

Answer 1

Now you posted more source code, I'm able to get you more information, but this will be a long one. This is also a very localized problem, so I'll try to answer as broadly as possible, for this answer to be useful for more people than only you.

General problem

First of all, let's resolve your primary problem - displaying only one kind of item instead of several different ones. Actually, this may be simply resolved by debugging your program - even manually, eg. tracing, where the program goes. Here we go:

*** main.cpp, 17 ***
findItem ->generate_item(d2, s2);

(...)

*** getItem.cpp, 49 ***

int rn = 0;
...
int cat_item = 0;
...
    if (rn == 0) // mushrooms
    {
        if(cat_item == 0)
        {
            listItem = new item;
            strcpy_s(listItem -> itemName, "an earthball mushroom");
            listItem -> itemDamage = d2;
            listItem -> itemStability = s2;
            listItems -> add_item(listItem);
        }
...

*** getItem.cpp, 148 - continuing ***

damage = d2;
stability = s2;

int j = rand();
for (int j =0; j <= 3; j++)
{
    cout << "\tJ equals: " << j << endl;
for (int i =0; i < listItems -> count(); i++)
    {   
        item *found = listItems -> Retrieve(i);
        cout << "\tYou have found " << found -> itemName << "." << endl;
        cout << "\tIt has a damage rating of " << found -> itemDamage;
        cout << " and a stability rating of " << found -> itemStability << "."<< endl;
        cout << endl;
    }
}

Here's, what your program does in the lines I specified:

• Calls findItem->generateItem;
• Sets rn to 0 and cat_item to 0
• Basing on rn and cat_item adds a single item to a list
• Tries to display random elements from list, but due to complicated condition inside getItem::Retreive, it always returns Head (it is the only element of the list anyway).

You don't add elements to list in a loop, so there's nothing surprising, that only one item displays.

Architectural issues

• Usage of a list is an awful idea in this case. You need an easy access to elements by their index and in this case a std::vector would be a lot better (faster, easier to maintain and use). Read more about usage of different data structures in C++11.

• You have some serious issues inside your genItem class. It looks like a repository for all available items, but then you do some very suspicious things inside, like:

  void genItem::generate_item(int d2, int s2)
  {
      genItem *listItems = new genItem();
  

  There is no point (in this case) in creating class instance inside itself. If genItem is supposed to serve as a container/repository for items, you shall instantiate it in main.cpp (or whoever is responsible for this object's lifetime) and use it there. The printing instructions look also like a hardcore debug code left during the battle with compiler.

• Your code is recoverable, but it would require much work, which I'll left to you. Read further about syntax/implementation problems.

Syntax / implementation problems

• You allocate objects and leave them be: it looks like you turned to C++ after writing in Java or C#. For example:

  int main()
  {   
      genItem *findItem = new genItem;
  
      int d2 = 0;
      int s2 = 0;
  
      findItem ->generate_item(d2, s2);
  
      cout << "\t"; system("pause");
      return 0;
  }
  

  You instantiate genItem, store a pointer to its instance in findItem variable, but then just leave it be. A live object left that way is considered to be a memory leak: noone will free that memory for you, this object will be kept alive until your program terminates even when you won't need it anymore. Notice, that you write such code in many places.

• Naming is unclear. What is d2, s2? Why d, s? Why 2? Disk space is very cheap these times and there is no reason to keep variable names so short and non-descriptive. Give them appropriate names (I guess, that in case of this example, they should be named: newDamage and newStability or similar

• You complicate code too much IMO. This loop:

  item *genItem::Retrieve(int position)
  {
      item *current = Head;
      for (int i = count() -1; i > position && current != NULL; i--)
      {
          current = current -> Next;
      }
      return current;
  }
  

  Can be written as following (for example):

  item *genItem::Retrieve(int position)
  {
      item * result = Head;
      while (result != nullptr && position > 0)
      {
          result = result->Next;
          position--;
      }
  
      return result;
  }
  

  The second version does the same (actually it works correctly, in contrast to your method) and is a lot better readable than the first version.

• Don't write in C:

  genItem::~genItem(void)
  

  It is valid C++, but the preferred version is:

  getItem::~getItem()
  

• Try not to use platform-specific solutions, such as: system("pause"); Your program may not be allowed to run external commands or programs and will crash - despite fact, that you run the external command for such simple task. If you want to stop the program from exiting, use another solution, such as getchar (or look up on SO, how to stop program from exiting immediately).

Simple example

Here's an example, how your problem might have been solved a lot easier:

#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>

class Item
{
public:
    std::string Name;
    int Damage;
    int Stability;

    Item(std::string newName, int newDamage, int newStability)
        : Name(newName), Damage(newDamage), Stability(newStability)
    {

    }
};

class ItemRepository
{
private:
    std::vector<Item> items;

public:
    ItemRepository()
    {
        Item item1("Mushroom", 10, 20);
        items.push_back(item1);
        Item item2("Rock", 100, 30);
        items.push_back(item2);
        Item item3("Piece of paper", 5, 2);
        items.push_back(item3);
    }

    const Item & GetRandomItem()
    {
        int index = rand() % items.size();
        return items[index];
    }
};

int main()
{   
    ItemRepository itemRepo;

    for (int i = 0; i < 10; i++)
    {
        const Item & item = itemRepo.GetRandomItem();

        std::cout << item.Name << ", Damage: " << 
            item.Damage << ", Stability: " << 
            item.Stability << "\n";
    }

    getchar();
}

Answer 2

Others have already pointed out that a linked list is probably inappropriate - it could be an appropriate choice in theory, but (1) for an adventure game it seems unlikely, and (2) it seems like premature optimisation anyway.

However, you can select n items randomly from a linked list, in a single pass, and with each item occurring with equal probability. You need to know in advance how many items there are, so if you don't know that, you need one extra pass to calculate that total before you do the selection.

For the first item, you can easily determine the probability of that item being included - it's n/N where n is how many items you want, and N is the number of items in the list. So choose whether to include or exclude the item on that basis.

For the rest of the list, you either still need n items or you need n-1, out of the N-1 items remaining. It's the same basic problem, just with a shorter list. So recurse. And as this is tail recursion, it works just fine as a loop too.

Intuition might suggest that the probabilities are wrong - that the probability of the second item shouldn't depend on whether the first item was selected or not - but intuition is wrong in this case. Do the math and this works perfectly. To reassure you, consider the probability of the second item being chosen as you'd express it before you choose the first.

The first item will either be selected or not. If the first item is selected, the probability of the second item being selected is (n-1)/(N-1). If the first item isn't selected, the probability of the second item being selected is n/(N-1). So we have...

P2 = (n/N)(n-1/N-1) + ((N-n)/N)(n/N-1)
   = (n^2 - n)/(N^2 - N) + (nN - n^2)/(N^2 - N)
   = (nN - n)/(N^2 - N)
   = n(N-1)/(N^2 - N)
   = n/N        because N^2 - N = N(N-1)

Similar logic applies for all positions in the list, provided it's actually possible (ie n <= N).

I'm sure this is a well-known algorithm with a name, but I don't remember the name at the moment.