Newb Question about rpg inventory management

[gamenovice]

Hey guys, i got a question about inventory management.

Before that, some setup:

currently there are 2 parts: the backpack, and the item classes. the item classes have inheritance setup, so for example Item is an abstract base class, and armor, weapon, and books are concrete subclasses.

the backpack acts like a container object for items. currently i use a 2d array of item pointers (because subclasses are of varying sizes and im doing this in c++).
the array is organized with each column(or first order of the array) being the item subtype, and each row(second order of array) actually holding the item references where the item type matches the subtype index. for example array[0] is for armor whereas array[1][j] is for books. this works pretty well if all you do is search by item type, since it already eliminates 1/subtype of the work when searching (all bets are off when you search the entire array for more general attributes).
it has basic add, remove, and searching implemented, which is very very reesty (but it works).

the problem is that i set out attempting to make the backpack polymorphic with items, but when i go to add, remove, or search, i end up inspecting the item type (which is made available as a data member from the base class) before i downcast and do the appropriate work to it. everytime i go through the code, my brain is telling me there has to be a better way to do this. not just that, but i dont have any sort of templating, so processing each subclass of item (there are 6 subclasses) requires its own if else branch of code. One bright side I suppose is that the actual searching is a little faster than blind array iteration, but how much faster is arguable.

now the purpose of the backpack is to have an inventory that can be searchable. currently this 'sorta works'. meaning, i have separate search methods for each stat of each item. the methods are organized from most general to specific(where item name is general and attack is specific since attack only applies to weapons). i say sorta works because with this system, i do have a feasible way to let the end user check specific stats one at a time, such as "show me all weapons with attack > 40" or "show me all items with type Consumable". but if i wanted to allow queries like "attack > 40 and item name contains monado", I'd have a tougher time implementing that, as it would quickly lead to a combinatoric explosion of functions i have to write. I will not even attempt to post the code here because my backpack class is over 1600 lines of code (an indicator that i already fucked up).

I should preface by saying I'm not the sole writer of the code, but I am a heavy contributor to the project (it was a college group project, so yea...).
the code is available for viewing on https://github.com/MysticsCode/inventory_system_project

If you guys know of better or more elegant ways of handling a similar rpg inventory system, I'd love to know. Same goes for if there are ways to dynamically handle item types as well as making searching faster and more diverse.

If something isn't clear let me know and I'll elaborate on it.

[gamenovice]

I am aware of the option of using databases, and in fact am considering using SQL Lite in the future. But I want to see if it's possible to devise a data structure or system first before I resort to databases.

[dandymcgee]

I am aware of the option of using databases, and in fact am considering using SQL Lite in the future. But I want to see if it's possible to devise a data structure or system first before I resort to databases.

I was just about to recommend that. Many RPGs with complex items will use some sort of database. In many cases, it's something significantly smaller than e.g. MySQL, and in some cases it may even be a custom rolled data storage format and query language. If the application is standalone (as opposed to online), SQLLite is probably a pretty good choice if you do go the database route.

If you were more interested in getting your hands dirty, you could define and implement your own simple querying language.

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

Here's a general idea of where I would start (based on SQL constructs):

Define a syntax

For the purpose of example, I'm going to define the following relatively simple syntax:

Code: Select all

std::string query = "attack > 40 AND item_name CONTAINS 'monado'";

Implement query parsing

Depending on the complexity of your syntax, your parser could be anything from a bunch of string splits, to regular expressions, to a full-on lexer with tokenization and optionally semantic analysis. To parse the above example you would need to split on logical operators (e.g. "AND", "OR"), then parse the individual statements (e.g. "attack > 40"). You could tokenize the operator aliases (e.g. replace all instances of ">" with "GREATER_THAN") if that would make parsing statements easier.

Example (Pulling this out of my asshole):

I might tokenize all logical operators (i.e. replace {" AND ", " OR "} with " {OPER} ")

Expression A:

Code: Select all

attack > 40 {OPER} item_name CONTAINS 'monado'

Syntax Checking and Semantic Analysis

Then tokenize comparators (i.e. replace {" > ", " < ", " = ", " CONTAINS "} with " {COMP} ")

Code: Select all

attack {COMP} 40 {OPER} item_name {COMP} 'monado'

Replace values (i.e. regex replace "\{COMP\} \d+" with "{COMP} {NUMBER}" and replace "\{COMP\} '\w+'" with "{COMP} {STRING}")

Expression B:

Code: Select all

attack {COMP} {NUMBER} {OPER} item_name {COMP} {STRING}

Save this expression for later.

Replace property names (i.e. regex replace "\w+ \{COMP\}" with "{PROP} {COMP}")

Code: Select all

{PROP} {COMP} {NUMBER} {OPER} {PROP} {COMP} {STRING}

Now you can validate the overall semantics of the expression. For instance, if you see "{PROP} {PROP}" or "{OPER} {COMP}" you know there's a general syntax error.

Then you can go back to saved expression B, and do type checking. Can the "attack" property be compared to a number? Can the "item_name" property be compared to a string?

(Alternatively, you can take the STDLIB approach and say "fuck the user, if they give me invalid syntax everything breaks horrifically".)

Parsing

Going back to Expression A, we can now split on " {OPER} " into an array of expressions:

Code: Select all

attack > 40

Handle one expression at a time. Save comparator then split on comparator (i.e. {" > ", " < ", " = ", " CONTAINS "}).
Now you have std::string prop, comp, value.

You could store this in a struct:

enum Comparator { GREATER_THAN, LESS_THAN, EQUALS, CONTAINS };

struct Expression {
    std::string prop;
    Comparator comp;
    std::string value;
};

struct Query {
    Expression[] expressions;
};

You could have a parent query struct to hold the expressions.

Then looking up items that match multiple search parameters ends up being something like (pseudo-code):

Item[] QueryItems(std::string query)
{
    Item[] result;

    bool itemIsMatch;
    foreach(Item* item in ItemMgr->GetItems())
    {
        itemIsMatch = true;
        foreach(expr in query->expressions)
        {
            if(!Compare(item, expr->prop, expr->comp, expr->value))
            {
                itemIsMatch = false;
                break;
            }
            
            if(itemIsMatch)
                result.Add(item);
        }
    }

    return result;
}

Helper function:

bool Compare(Item* item, std::string prop, Comparator comp, std::string value)
{
    std::string actualValue;

    //TODO: Switch prop, get actual property value
    if(prop == "attack")
        return Compare(item->attack, comp, (int)value); //Cast "value" to match real type
    else if(prop == "item_name)
        return Compare(item->item_name, comp, value);
}

bool Compare(int actualValue, Comparator comp, int value)
{
    //TODO: Switch comp, implement logic for each comparator, return true/false
}

bool Compare(std::string actualValue, Comparator comp, std::string value)
{
    //TODO: Switch comp, implement logic for each comparator, return true/false
}

Anyways, this is basically reinventing the wheel so I'm going to stop here. I just wanted to give a general idea of one way you might achieve this. Obviously, I would recommend SQLLite over this approach in any sort of deadline-ridden production project, but if you're just screwing around for the sake of learning you might have fun trying it the hard way.

Let me know if you have any questions, and be sure to show us what you come up with.

[gamenovice]

Now that I think about it, I feel like this sort of idea is what I had in mind for the query portion of the inventory system, though I may have very simplistic syntax depending on how difficult it'd be to do it. I might as well go ahead and screw around with SQLLite and try this out, since it's after the project due date anyway.Also do you happen to know any open source query language projects? I'd love to take a look at one sometime (call me an idiot if SQL happens to be one... I'm not too familiar with query languages and this is my first venture)

[dandymcgee]

Also do you happen to know any open source query language projects? I'd love to take a look at one sometime..

I can't think of any off the top of my head.

..(call me an idiot if SQL happens to be one... I'm not too familiar with query languages and this is my first venture)

SQL isn't an implementation, it's a language definition. There are many DBMS products: Oracle RDB, MySQL, SQL Server, etc. and each supports a different subset of database engines. MySQL is powered by the InnoDB engine, for instance.

It's also worth mentioning that in many cases a query language might be overkill. There are plenty of ways to find objects by property value using traditional data structures. For example:http://stackoverflow.com/questions/7042 ... n-a-stdset

Edit: I searched around a bit and found an interesting library called cpplinq that essentially aims to emulate C#'s LINQ capabilities in C++. This might provide some insights into how you could implement your own. You can find the source code here.

A LINQ query in C# might look like this:

List<Item> matches =
    (from item in ItemMgr.GetItems()
    where item.Attack > 40
    and item.ItemName.Contains("monado")
    select item).ToList();

Using cpplinq in C++11 it becomes something like:

auto result =    from_array (ItemMgr.GetItems())
              >> where ([](Item* item) {return (item->attack > 40 && strContains(item->item_name, "monado"));})
              ;

[K-Bal]

I didn't thoroughly read the whole SQL part, but I just wanted to point out that using inheritance for different item types might not be a good idea, in the same way that inheritance is not a good model for different game entities. Also how big can a game inventory possibly be that search performance even becomes an issue?

[gamenovice]

I didn't thoroughly read the whole SQL part, but I just wanted to point out that using inheritance for different item types might not be a good idea, in the same way that inheritance is not a good model for different game entities. Also how big can a game inventory possibly be that search performance even becomes an issue?

search performance probably won't be an issue, but its nice to make it optimized (assuming you do it correctly...).
I feel like you're right about the inheritance part, but I'm not sure why that is the case. would you care to elaborate?

[K-Bal]

When you start adding more items with different properties, everything becomes a big mess. Imagine a wizard that gets armor bonus for carrying some spell book. What type is it; Armor, weapon or book? Instead think about what an item really is: a collection of properties that have certain effects in the game world.

[gamenovice]

so i could use the component model for that instead? well it takes away the need of polymorphism, but it seems like that would solve my big problem of type checking before downcasting

[dandymcgee]

so i could use the component model for that instead? well it takes away the need of polymorphism, but it seems like that would solve my big problem of type checking before downcasting

One of my favorite articles on this subject is Evolve Your Hierarchy, which inspired my component based engine prototype.

[gamenovice]

Loving the way the source code is organized. Makes it really easy to understand how the component system works.... is it ok if i use this code to learn more about components?

[dandymcgee]

Loving the way the source code is organized. Makes it really easy to understand how the component system works.... is it ok if i use this code to learn more about components?

I should probably license my GitHub code properly so people don't need to ask this but:

http://www.wtfpl.net/about/

DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004

Copyright (C) 2015 Dan Bechard

Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.

DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

0. You just DO WHAT THE FUCK YOU WANT TO.