Gw Temp

Menu

Tutorial - 'Sorting in RPGMaker 2000' by Rast

An item about RPGMaker 2000 posted on

Blurb

Rast pumps out another fantastic advanced tutorial. Check this out to see how to sort variables (Good for when making Custom Menu Systems)

Body

This tutorial demonstrates how to sort a list of variables. The algorithm presented here is both fast and efficient, as it only makes a single pass through the item list for each item slot. This algorithm sorts the list in-place and does not require a secondary sorting list. Although this demonstration sorts in ascending order on a list of a fixed size, you can easily modify it sort in decending order and on growable lists.

This algorithm expects zero to indicate an empty slot. Zero values will be moved to the end of the list. This algorithm uses pointers to operate - you'll need to know how they work to implement an actual sorting event into your own game.

You'll need to use these variables for this sorting method:

CV - Current Value. This is the value of the last item sorted on the list, and will be zero when you start, or the value of the smallest already sorted item. The algorithm looks for the next higher value item on the list during each trip through the sort loop and places this item in the next slot.

CSL - Current Swap Location. This variable points at the variable that will recieve the sorted information. This starts at the beginning of your list and works its way towards the end as the list is sorted.

CRL - Current Search Location. The variable points at the list item currently being considered.

CMV - Current Minimum Value. This variable contains the value of the smallest non-zero list item found so far on this sort loop.

CRP - Current Result Pointer. This variable contains a pointer to the smallest non-zero list item found so far on this sort
loop.

SWV - Search Work Variable. This variable contains temporary data and it's use will depend on how it is being used.

And now the algorithm:

** We do some initial set up here. We set the current value variables to their starting values, so the list will sort starting from the first non-zero value from the beginning of the list **
CV = 0
CSL = Pointer to first item on the list

** This cycle sorts the entire list. When this cycle is done, the list is sorted. **
\CYCLE\

** We set CRL to CSL so that already sorted items are excluded from the sorting pass. The item being pointed at by CSL will be swapped with whatever CRL ends up being at the end of the sort loop. If the list is already in order, this will cause the item to be swapped with itself, which is no big deal. CMV must be set to a value that is higher than any value on the list. The loop will search for the lowest value by comparing each item to see if it is lower than this value but higher than CV, which will hold the value of the last sorted item, thus, the value in CMV at the end of a sorting pass will be next higher value item on the list than the last sorted item. CRP is set to -1. At the end of a sorting pass this variable will hold the ID number of the variable that held the next highest value (which is stored in CMV). If no item is found (i.e. the entire list has been sorted and all that's left are zeroes at the end of the list), this variable will still be -1 at the end of a sorting pass and this tells us the list has been sorted and we do not need to continue. **
\CRL = CSL\
\CMV = Value higher than highest item on the list (9999 or some such)\
\CRP = -1\

** This cycle goes through the list and compares each item from CSL forward to see if it is larger than CV and less than CMV. If it is it's value and pointer are stored in CMV and CRP respectivly. And at the end of this cycle, these variables will hold the ID and value of the next highest variable on the list. **
[CYCLE]
[SWV = Value being pointed at by CRL]

{If SWV < CMV}
(If SWV > CV)

(CMV = SWV)
(CRP = CRL)

(End Case)
{End Case}

{If CRL = ID Number of Last Variable on List}
{Break Cycle}
{End Case}

[CRL + 1]
[End Cycle]

** At this point, CRL should be a valid pointer. If it is still -1, we know that we have sorted all items on the list and any remaining items do not hold any data (are all zero). We're done and we break the cycle **
{If CRL = -1}
{Break Cycle}
{End Case}

** These three lines swap the values in the variables being pointed at by CSL and CRL **
\SWV = Value being pointed at by CSL\
\Value being pointed at by CSL = Value being pointed at by CRL\
\Value being pointed at by CRL = SWV\

** We set CV to CMV as the next valid item to be sorted must have a value higher than the last found item **
\CV = CMV\

** We increment CSL by one to point at the next slot on the list to recieve sorted data **
\CSL + 1\

** We check to see if CSL has gone beyond the end of list. If the list is full, this will cause the sorting cycle to terminate after it has sorted the last item **
{If CSL > ID Number of last variable on the list}
{Break Cycle}
{End Case}

\End Cycle\

The applications for this are primarily in custom lists, such as CMS item and skill lists and the like, although this can be useful anywhere you need sort something. This algorithm is based on the Item List Sorting event in Dragon Destiny II. This is not verbatim from DD2 as DD2 uses multiplexed variables to store item data, which adds a level of complexity unnecessary for this tutorial, which is already intricate enough. Still though - you should find it useful for your own custom lists.