About Trading

[hidari_hand]

That's pretty significant if it recalculates every 5 minutes. Just to clarify, you're saying that the quantity and prices vary according to the high/low-stock system I describe every 5 minutes?

I'm sorry for the very late responds..
Yes, I am.
In fact, I'm also quite surprised about this system.

Could you further remark on your testing methodology, hidari_hand? I was not able to reproduce your results for a 5 minute interval; the smallest update interval I uncovered with some basic testing was 15 minutes. I tried:

Here's how I was done it.
-Try initiate trading post npc dialog.
-Remark every price and quantity.
-Exit dialog.
-Run the stopwatch
-I can just stand in front of the npc or walking around the trading post or walking arount the town etc.
-After 300 seconds.
-Try initiate the dialog.
-Watch any different price and quantity.

Just to clarify, the 5 minutes is in real world.

Also I'll update the first post with your newest finding..

[Omnigamer]

Which town were you testing with? It's possible that the timer could be different per town. I was using South Window during the first point in the story that it's available.

[hidari_hand]

Which town were you testing with? It's possible that the timer could be different per town. I was using South Window during the first point in the story that it's available.

The Kobold Village one..

[Omnigamer]

Just as a heads-up, I re-tested both cities. The time for a SW refresh is 15 minutes, and for Kobold Village it is in fact just 5 minutes. So it is different for each storefront. Each refresh also behaves differently than the initial stocking in terms of quantities and prices.

I also started re-familiarizing myself with IDA for the SHOP modules. I've isolated the main functions that deal with sourcing the quantity and price in KOUEKI1.bin but there's still a fair bit more analysis to do before I understand the checks and where any of the data tables are. At the very least, I can confirm that there are two RNG calls for each item: one for the quantity, and one for the small random fluctuation in price. More info to come.

[Omnigamer]

So I went through the code. It's kind of ugly, but I think I've narrowed down most of the variables. The blocks are too long to make any sense of from printing here, so I put it into pseudocode instead.

EDIT: Correct version below.

So yeah, an awful lot of checks all the time. The summary points are as follows:

-A lot of it depends on your game time. It takes in your current game time in minutes after the first NPC dialog and uses it for some of the calculations. It compares with your prior access time of the shop to determine when to update; in the few examples I've tested, this is usually 5 minutes.
-Going from the above, your prior access time of 0 for a first opening has a pretty significant impact on the initial item stock and price since it maxes out the multipliers for both.
-Item quantity has a small amount of randomness, usually varying 0-3.
-Price has a lot going on. Basically, there are set floors and ceilings based on the standard price. They also apply discounts or penalties at different points based on the shop. The randomness for price though is the 0-11 added on to the final value as I described before.
-The "Other Stuff" has me slightly concerned yet. There are a pair of other subroutines that it calls at a certain decision point that I haven't spent any time investigating. It may have to do with when prices already exist.

I need to clear my head a bit and decide whether to hunt down the data tables used for the standard_quantities etc statically or just compile all of the data dynamically by visiting the shops. If it happens, it will happen later in the week. I have a fully commented disassmbly available too, but I'll save you all from looking at the mess unless you really have a vested interest in peeking through.

EDIT: Re-reading it now, I notice some inconsistencies/inaccuracies. I can't look back at the code until this evening, so I'll update it then. In particular, there are some missing checks/bounding on the Quantity.

[Pyriel]

(price_mod * 0x55555556) - (price_mod >> 0x1F)

Multiplying by 0x55555556 is dividing by 3. 0xAAAAAAAB is 2/3. Subtracting the sign bit (price_mod >> 0x1F) is just an adjustment for if price_mod is negative.

Ignore explanation below if you don't care.

OK, firstly there's a difference between MFHI and MFLO. With division, register HI contains the remainder, while LO has the quotient. With multiplication HI contains the upper 32-bits while LO has the lower 32. At some point the MIPS processors started supporting 3 register multiply and divide operations, where the target register contains either the product or the quotient, but HI and LO are always loaded anyway. IDA will often show register zero as the target register when only the two input registers are specified. I'm positive that after the above multiply is done, the value on HI will be retrieved rather than LO. Why's that important? Well...

Small history lesson: Most simple operations on a MIPS processor take 1-3 cycles (an unachievable goal of RISC is all operations take 1). However, multiplication and division are complex enough that they take several times that. I forget how long they go on MIPS, but 8-32 cycles for a multiply was pretty common in this generation of processors. I think the R3000 in the Playstation was around 8-16, so not too bad. And it's asynchronous, so you can issue the multiply operation, and do other things instead of just waiting on the result. A divide on the other hand, can take from 64-256 cycles. Even done asynchronously, and assuming a minimum number of cycles, you're likely to need the result before the operation completes. This will cause a register stall and force processing to stop until the results are available. In a video game, which is loops running on top of loops that have to poll input and perform tasks several times a second, a divide is obviously something you want to avoid.

One way around using divide is to use shifts, adds, multiplies and other operations. Right-shifting will work on simple power-of-two division, but it gets fancier for say division by 3. You can use a two's complement inverse to multiply by certain values quite easily, and then use shifts and adds to get to others, all at a significantly lower cost than a single divide operation. On the PSX you multiply by very large numbers, which will force a quotient value into the HI register. So if you see multiplication by an enormous constant, followed by MFHI, you can be almost certain that this is the compiler avoiding DIV at all costs.

It only works with constants, so if you see an actual DIV in a PSX game, it's most likely because the divisor can be changed during play.

You'll see this with multiplication too. For example, it's quicker to do (a << 1) + a than 3 * a. So the compiler will opt for the former when 3 is expressly a constant.

[Omnigamer]

Ah, I was not aware that MIPS handled division differently from multiplication in terms of the registers. That should simplify a bit of the logic. This subroutine at least only uses mult/div with two registers so it's always taking from hi/lo. I knew about the sign bit adjustment, but there wasn't a pretty way to write it out in C-like pseudocode.

I started compiling the data tables via breakpoints. What I initially assumed to be shop discounts or penalties seem to be 0 for every single item so far, so I'm not sure what to make of them. It could be something that comes into play after initialization though, so I'll keep an eye out for it. The "sets" that I mention could also just be the refresh_period for the item, but I need to double check since they index it differently. KOUEKI2 subroutines are identical to KOUEKI1, just a different starting offset (10DC50 instead of 15DC50).

[Omnigamer]

Fixed it all up and simplified it a bit.

Code: Select all

SHOP PSEUDOCODE



cur_time = Get_Minutes();

last_accessed = shop.last_accessed;



if(last_accessed > cur_time)

	cur_time = 1;

	

time_dif = cur_time - last_accessed;



if(time_dif < shop.refresh_period){

	Skip_Updates();

	return;

}

else{

	for(i=0;i<shop.total_items;i++){

		

		new_quantity = shop.item[i].current_quantity;

		

		if(item[i].refresh_period <= time_dif){

		

			if(item[i].standard_quantity > shop.item[i].current_quantity){ //try to normalize towards standard

				new_quantity += time_dif/item[i].refresh_period;

				

				if(new_quantity > item[i].standard_quantity)

					new_quantity = item[i].standard_quantity; //If you overshoot, then just set to standard

			}

			else{

				new_quantity -= time_dif/item[i].refresh_period;

				

				if(new_quantity < item[i].standard_quantity)

					new_quantity = item[i].standard_quantity;

			}

			

			quantity_rand = RNG(-1:1);

			

			temp = quantity_rand * item[i].swing; //multiply sets by RNG

			

			new_quantity = abs(new_quantity + temp - (item[i].swing/2));

			

		}

		

		price_mod = item[i].standard_price * (item[i].standard_quantity - new_quantity);

		

		if(item[i].standard_quantity > 2){

			price_mod = price_mod / item[i].standard_quantity; //if it's a high-stock item, divide price_mod

		}

		else{

			price_mod = abs((price_mod / 3)); //otherwise divide by 3

		}

		

		price_mod+= item[i].standard_price;

		

		if(price_mod > 65000)

			price_mod = 65000;

			

		refresh_cycles = time_dif / shop.refresh_period;

		

		if(refresh_cycles > 4)

			refresh_cycles = 4; //Cap refresh_cycles to 4

			

		final_price = (price_mod - shop.item[i].prior_price) * refresh_cycles;

		

		if(final_price < 0)

			final_price+=3;

			

		final_price = final_price/4; //Divide by 4

		

		price_rand = RNG(0:10);

		

		final_price = price_rand + shop.item[i].prior_price+ price_rand - 5;

		

		other_price = (2/3) * item[i].standard_price;

		

		if(final_price < (other_price/2))

			final_price = (other_price/2);

			

		if(final_price>65000)

			final_price = 65000;

			

		item[i].current_price = final_price;

		item[i].current_quantity = new_quantity;

	}

}

I was missing a few key details in the prior version. Before purchasing for the first time, the initialization code is fairly straightforward. The main idea is that price is set based on the new quantity, which has one of three possible values from the RNG. The "swing" of an item is the amount that it varies as a result of this RNG. It is centered at 0, but the "high-stock" value should be about half of the swing value above the standard quantity, while the "low-stock" value will be 1.5x the swing value below the standard. The average case is .5x swing value below standard. Price follows pretty simply for initialization.

If you're revisiting the shop, however, things get a bit trickier. Items follow a "restocking" or "consumption" pattern if you've bought/sold the good before. You can think of it as the shop gradually moving back towards its standard quantity, either by consuming excess goods or accumulating missing stock. This would normally by awesome, however the shop also keeps track of the last price you purchased your good for and uses it as part of the calculations. This prevents the price from suddenly skyrocketing if you buy up all their goods; the change is gradual, and only accumulates as the shop cycles accumulate. It's critical to note that the shop cycle is what determines the pricing, and not the item cycles.

I have full tables for the trading posts with the standard quantities, prices, sets, and refresh periods. You can check them out here:

https://docs.google.com/spreadsheets/d/ ... sp=sharing

As far as analysis of this, I'm still working on it. I at least reproduced something to predict shop prices, but I might just be missing something as far as the quantity RNG. Looking at the code it seems like there should be 3 distinct possibilities, but in practice I only seem to ever see 2. As far as I can tell the math doesn't try to make the RNG value positive, so I'm not sure why it doesn't show up. In any case, this should get us started on determining best trading practices.

EDIT: Below is the disassembly block related to that RNG call, so let me know if I missed something along the way.

Code: Select all

ROM:0010E714 Quantity_RNG:                            # CODE XREF: sub_10E4CC:loc_10E708j

ROM:0010E714                 ori     $2, 0x4C2C       # Set up RNG Call

ROM:0010E718                 lui     $8, 0x8012

ROM:0010E71C                 jalr    $2               # RNG CALL 1, loaded into r2

ROM:0010E720                 sw      $2, 0x8012008C

ROM:0010E724                 andi    $18, ITEM_COUNT, 0xFF

ROM:0010E728                 sll     $3, $18, 1

ROM:0010E72C                 addu    $3, $18

ROM:0010E730                 sll     $3, 2            # Address stuff

ROM:0010E734                 addu    $3, TRADER_ADDRESS, $3  # Add to base addr (80016bd0)

ROM:0010E738                 lbu     $3, 0xBC($3)

ROM:0010E73C                 move    $4, $2           # Hang on to it for later

ROM:0010E740                 sll     $2, $3, 2

ROM:0010E744                 addu    $2, $3

ROM:0010E748                 sll     $2, 1            

ROM:0010E74C                 addu    $2, $22         #set up addresses and structure indexing

ROM:0010E750                 lbu     $5, 4($2)        # Item swing

ROM:0010E754                 bgez    $4, loc_10E764   # If RNG positive... branch

ROM:0010E758                 sra     $2, $4, 14       # If RNG negative...

ROM:0010E75C                 addiu   $4, 0x3FFF       # Add 0x3FFF to value before right shifting

ROM:0010E760                 sra     $2, $4, 14

ROM:0010E764

ROM:0010E764 loc_10E764:                              # CODE XREF: sub_10E4CC+288j

ROM:0010E764                 mult    $5, $2           # Mult by -1,0, or 1

ROM:0010E768                 srl     $2, $5, 1        # Cut Swing in half...

ROM:0010E76C                 andi    Final_Price, $23, 0xFF

ROM:0010E770                 mflo    $8

ROM:0010E774                 addu    $3, Final_Quantity, $8  # Add mult amount to prior quantity

ROM:0010E778                 subu    Final_Quantity, $3, $2  # then subtract half of the swing

EDIT2: Running through a few things for price, there are still some inconsistencies, most notably when the standard quantity is -1. I'll keep trying to iron it out.

EDIT3: Figured out why the negative branch for the random quantity adjustment never gets hit. The RNG function they use ANDs the result with 0x7FFF before passing it along. This makes it so that it will never get interpreted as a negative value, and thus the RNG will only ever turn out to be 0 or 1, instead of a spread between 0, 1, and -1. It works out fine in the end, but it may be a bug since they pretty obviously tried to account for it in the code. Either that or it is an artifact from different points in development.

[Omnigamer]

OK, so the below is specifically related to speedrunning routing, but the ideas should be useful for other folks going forward. It describes the route to trade just enough in a minimal number of trips and regardless of luck in order to hit the 50k profit needed to recruit Gordon. The main strategy involves short trading, which is most effective at Highway Village.

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

Without having done any actual testing yet, I think I have a completely consistent trading strategy. It centers on the fact that Highway is a fantastic short-sale trading center. What I mean by this is that the shop refresh period is very fast compared to most of the item refresh rate, especially the ones that are already particularly valuable there. So you can buy up the stock and then come back between 12 and 14 minutes later and reap the rewards. It can be expanded up to 15 minutes instead of 14 with some extra trading, but I haven't tuned the actual window for that yet in terms of traveling around.

I'll go into more details as necessary, but the general route is as follows:

-Buy all Mayo and Native Costumes in South Window during your first visit.
-During second visit to South Window (Adlai + others recruiting), buy up Mayo and Costumes until you have 6 and 4, respectively.
-During Forest Village visit (Wakaba and Tony recruiting) buy all Native Costumes.
-On first visit to Highway, if Mayo is high price (~2750) sell all. Otherwise buy all. Buy all native costumes, gold bar, and all Deer Antlers.
-On second visit, exactly 12-14 minutes after first visit, sell everything you have.

At least as far as I've calculated so far, this strategy should net you 50k even with the worst possible RNG sets. The big caveat is making that timing window, which needs to be figured out yet. Another downside is that in a worst-case scenario for inventory space, 26 slots are taken up by items. This can be tuned a little bit and I haven't looked at each individual possibility, but having only 4 slots left for other items could be a bit unfortunate. In any case, I'll try to think it out a bit more tomorrow when I have more sleep in me.