Request for Comment: Implementing a Hash Table in ChoiceScript?

I remember years ago (before arrays were a thing) some poster asking how they could create a *gosub to create variables during runtime, as in while the game was runninh.

Something like:

`*label loop_create
*temp i 1

*if i < 101

    *create my_var${i} "procedural_stuff"
    *goto loop_create
`

Recently my girl give birth to a baby boy, and as is expected, my life turned upside-down and my non existent free time turned negative. So as I was reminiscing of my past mistakes towards Data Handling in ChoiceScript, I’ve got a epiphany!

A lighting hit me and a cobra bite my ankle and I wrote this little code in a piece of napkin (more or less. I mostly work my code on scrap paper, since I have no PC)

Here the code, just create a scene named cs_hash copy and paste the following code there and u re good to go:

Summary


*label set_table 
*params table_name max
*temp index 1
*temp table_length ("${table_name}_1")
*set {table_length} max
*temp index_address ("${table_name}_${max}")
*set {index_address} index
*temp max_entries (max/2)

*comment Metadata: Stores max array length and initial index
*return

*label set_key_value
*params key value table_name
*gosub load_table_info
*gosub check_if_key_exists
*if found
  *comment Key already exists; updating value at current address
  *temp address_val ("${table_name}_${(j)}")
  *set {address_val} value
  *return
*if index < max_entries
  *gosub store_new_key_value
  *return
*if index = max_entries
  *bug OVERFLOW: Table "${table_name}" exceeded maximum ${max_entries} entries.
*else
  Error encountered in setting key-value pair.
  *return

*label get_key_value
*params key table_name
*gosub load_table_info
*gosub check_if_key_exists
*goto return_value

*label check_if_key_exists
*temp found false
*temp i 2
*temp j 1
*temp checked_address ""
*label loop
*if i > index
  *return
*set checked_address ("${table_name}_${i}")
*if ({checked_address} = key)
  *set return ("${table_name}_${(max - i)}")
  *set found true
  *return
*else
  *set i + 1
  *set j + 1
  *goto loop

*label return_value
*if found
  *set return {return}
  *return
*else
  Key not found!
  *return

*label load_table_info
*temp max_addr ("${table_name}_1")
*temp max {max_addr}
*temp index_address ("${table_name}_${max}")
*temp index {index_address}
*temp max_entries (max / 2)
*temp key_address ""
*temp value_address ""
*return

*label store_new_key_value
*temp current_index (max - index)
*temp current_address ("${table_name}_${current_index}")
*set {current_address} value
*set index +1
*set current_address ("${table_name}_${index}")
*set {current_address} key
*temp index_address ("${table_name}_${max}")
*set {index_address} index
*return

*label print_table
*params table_name
*gosub load_table_info
*temp i 2
*temp j 1
This is a List of the touples declared on your ${table_name} table:
*line_break
*label print_loop
*if i > index
  *return
*set key_address ("${table_name}_${i}")
*set value_address ("${table_name}_${(max - i)}")
Key[${j}]: ${({key_address})} 
| Value[${j}]: ${{value_address}}
*line_break
*set i + 1
*set j + 1
*goto print_loop
*return



“Efficient”(cough! coughs!) Hash data Management in ChoiceScript

=======Ă·=======Ă·=======

TL;DR

This code offers a way to manage key-value pairs (similar to a hash table) in ChoiceScript. It enables developers to store and retrieve data dynamically without needing to create variables upfront.

Introduction

Managing a large number of variables in ChoiceScript has long been a headache, especially if you’re generating content procedurally. Imagine a character list with unique traits, or an evolving inventory – tracking all that with manually declared variables can get messy fast!

This code offers a solution. Using a single array and a few helper functions, you can efficiently store, update, and retrieve key-value pairs. No more gambiarrared code or constant re-declaration of variables – just a clean, flexible storage system.

ChoiceScript code implements a simple key-value store with the following features:

Key Features

  1. Table Initialization : *gosub_scene cs_hash set_table (table_name);(set_table): Sets up a “table” array with a specified maximum size, tracking both its total and current entry count.

  2. Key-value pair management: *label set_key_value and *label get_key_value allow setting and retrieving values by key.

  3. Overflow detection: Prevents exceeding the maximum table size.

  4. Key existence checking: *label check_if_key_exists verifies key presence.

  5. Table printing: *label print_table Table Printing (print_table): Lists all stored key-value pairs for easy debugging.

=========================

It uses metadata to track array length and current entries, minimizing the need for separate variables. A print_table function is included to list all stored key-value pairs.


ChoiceScript developers often encounter challenges when trying to manage numerous variables, especially in games with procedurally generated or dynamic content, like NPCs or other customizable assets. The limitations around creating variables dynamically in ChoiceScript can lead to bulky and repetitive code when managing multiple attributes.

This solution introduces a method for storing and retrieving key-value pairs using a single array.

It aims to facilitate developers to:

  1. Store data (key-value pairs) without creating individual variables for each attribute. (And saving time to write the actual story of the damn game!)

  2. Dynamically check for existing keys, update values if needed, and store new ones if the key does not exist. (In other words, Overwrite!)

  3. Retrieve values efficiently based on keys, making it easy to query stored information.

  4. Display all stored tuples in a “readable” (meh) list format, using the print_table function.

Core Functions Explained

*gosub_scene cs_hash set_table (new_table)

Table Initialization (set_table): This function sets up an array with metadata to track the maximum length and number of entries. It creates a “table” array that can hold up to half the specified length in key-value pairs, as each tuple requires two positions (one for key, one for value).

*gosub_scene cs_hash set_key_value (key) (value) ("new_table")

Adding or Updating Entries (set_key_value): This function takes a key, value, and table name.
If the key exists, it updates the value. If not, it stores the new thingy at the next available slot. The function also checks for overflow, returning an error message if the table is full.

Retrieving Values :

*gosub_scene cs_hash get_key_value (key) ("new_table")

(get_key_value): This function searches for a specified key in the table and retrieves the associated value if found, or returns a “Key not found!” message if the key doesn’t exist.

Displaying the Table:

*gosub_scene cs_hash print_table ("new_table")

(print_table): This utility function lists all key-value pairs currently stored in the table, useful for debugging and checking the current state of your pair.

Example Usage

Below is an example of how this tuple system can be used to add, update, and retrieve entries:

*create return ""
*comment return is a global
*comment variable necessary
*comment whithout it, cs_tuple
*comment will not work properly 
*create_array table 1000 ""
*temp max_table_length 1000

*gosub_scene cs_hash set_table ("table") (max_table_length)

*temp key "npc_name"
*temp value "Alice"
*gosub_scene cs_hash set_key_value (key) (value) ("table")

*temp key "npc_age"
*temp value 25
*gosub_scene cs_hash set_key_value (key) (value) ("table")

*gosub_scene cs_hash get_key_value ("npc_name") ("table")
The retrieved name is: ${return}

*gosub_scene cs_hash print_table (table_name)

Why This Approach?

This setup is particularly useful for developers who need a scalable way to manage dynamic data in ChoiceScript without declaring numerous variables upfront. It’s ideal for games that involve randomly generated content or need flexibility to manage attributes in a structured yet compact way.

Feedback?

I’d love any feedback or suggestions on optimizing this further. I aimed to keep the code structure simple and maintainable while making it functional for practical use cases in ChoiceScript.


Check this out! :smiley:

OOnStartup.txt:

*title Tuples
*author mème
*create_array table 1000 ""
*create return ""
*create key "new_varname"
*create value "159641.6"
*temp max_table_lenght 1000

*temp this_table_name "table"


*gosub_scene cs_hash set_table (this_table_name) (max_table_lenght )

Now, lets store variables in this table!


*gosub_scene cs_hash set_key_value (key) (value) ("table")
*temp k 1

*comment Le me creates procedurally a bunch
*comment of variables using a loop!?
*label k_loop
*if k < 30
  *set key "k_${k}"
  *set value ((this_table_name)&k) 
  *gosub_scene cs_hash set_key_value (key) (value) ("table")
  *set k + 1 
  *goto k_loop

*gosub_scene cs_hash get_key_value ("k_21") (this_table_name)
*set value return
*comment get_key_value returns value

k_21 value -> ${return}

*temp table_name "table"

*gosub_scene cs_hash print_table (this_table_name)

*finish

Example Use Cases

  1. Character stats management.
  2. Inventory systems.
  3. Game configuration storage.
  4. Dunno, you tell me! :smiley:

Feedback Wanted!

I’m looking to improve this approach. Suggestions on optimizing for performance or simplifying further are welcome!

1 Like

Hey @Nahim_Kerman ,

Nice work, I can see you’ve put a lot of effort and thought into this.

Some initial feedback below.

  1. I don’t think “tuples” is the right term here.

A tuple is typically just a list of values without any key (you can have named tuples, but it’s not as common). You’re probably thinking of a hash map/hash table? You do use the word table on occasion, including in your “method” names. tl;dr I’d drop the usage of “Tuple”.

  1. Whilst I can certainly see the appeal with the functionality, it’s worth noting to users that this will come at a potentially significant performance cost. Typically hash maps (and normal cs variable accesses) are of constant access time (no matter the size of the table/how many cs variables you have), but by using an array the access time is directly correlated to the number of items in the array. In short, the more you use this, the less performant your game is going to get. I don’t know how that will affect things in the real world, but I think it’s an important disclaimer to make note of.

  2. If there is a strong appetite for this I’d also suggest you re-write it as a CSLIB module. There are a number of benefits to this, but I think the two most important are a). Keeping all useful CS code utilities co-located and easy to find and combine and b). It has a test framework you should use so that people can have confidence your code is well tested and reliable before including it in their game. Happy to help with this if it’s of interest.

Nice work though!

1 Like

Parabéns pelo bebê!

I once tried to emulate classes with the Lua approach, but using arrays, but then I realized I was over complicating stuff just out of habit. :joy: It’s a nice mental exercise though.

1 Like

Thanks for the feedback!

Call me dumb, but I am not really a programmer so… well I kind of always assumed tuple was some Munchhausen’s baron tech slang (like Bootstrap or just, you know, Boot?) for pairs.

Yep I thought tuple was French for “pair”… (it sounds like it could be, right?).

Hash tables (or key-value stores) are specifically about connecting a unique key (like a name or ID) with a value (like a stat, item, or description), which is why it’s probably a more fitting term for what I’m trying building.

Sorry :disappointed:

A minor nitpick, but this sounds like a map (c++) or a dictionary (python), not hash table.

A map stores associated (unique) keys and values, with keys being potentially/typically strings. Meantime a hash table uses a “hash” generated from the original key (which is not preserved) for lookups, generally to improve performance (as it allows e.g. to convert string of any length into a fixed length numerical value)

1 Like

In mathematics, a tuple is an ordered sequence of values

I’m not sure about any french eytymology.

A minor nitpick, but this sounds like a map (c++) or a dictionary (python), not hash table.

You’re right so far as-in no hashing takes place in this implementation, so yes, Dictionary or Map would be a more appropriate name. But you’re conflating data structures and implementations. Python’s Dictionary data structures are implemented via hash tables. They are not two distinct concepts.

3 Likes

Putting my nerd glasses on. It’s not French. It’s derived from a misunderstanding of words such as quintuple, sextuple, septuple, etc. It’s from the number + “plus”, for example, quintus (five) + plus (fold/times/more). So, quintuple literally means fivefold. And tuple came from that as a fixed length collection.