Some sort of routing algorithm..

[Lemmy]

This seems to be the place where to coders hangout...even though it's been dead for a month..
Anyway, i'm working on something of a trade simulator and am designing an algorithm to assign AI freighters to pick up cargo and sell it somewhere, so that the profit is maximized.

I was wondering how some of the coders here would handle this.

The pathfinding isn't a problem, you can assume that finding a path and determining the distance between 2 locations is easily computable.

There are a certain amount of freighters, each located somewhere on the map.
Freighters have a cost of moving, the cost is linear to the distance travelled.
Freighters also have an upkeep cost, this is linear to the amount of time passed.
Furthermore there are ports. Each port sells and buy items for a certain price, the price for an item can be different at different ports.

I'm probably looking for some kind of approximation to the optimum here, since computing it exactly would most likely take too long.

Some thoughts i had about it:
Freighters only look for a trade route within a certain distance of their current location, and then it simply compares all possible routes within that distance.
However, the freighter might want to end its route at the same location of the start of another route: planning ahead...but that isn't really reliable because other freighters could take that new route before the first freighter gets there. doing it properly then and taking that into account would become too complex as far as i can tell. So i'm forgetting about planning ahead for now.

Soo....any suggestions

[LDiCesare]

I may be dumb, but I'm not sure I understand exactly what you want so forgive me if that's totally off.
You have ports with freight inside, and freighters which can carry the freight.
For each good, you can compute the best cost you will get for it, by looking at the cost in every port, the difference of costs and then subtracting the distance cost. Since both cost of moving and upkeep cost are linear on distance/time, they are a well-defined unchanging feature of the path used.
Once you've computed that, you have a set of paths, each with a cost/revenue. A freighter would look at the nearest port, look at the best route from that port and choose it.
Better, a freighter would look for the best route in the world, look where the starting port is, then decide to pick the best route from where it is to the starting port of the best route.

The real problem here is not algorithmic but economic: There must be a limited amount of supplies to carry otherwise everyone will trade the same good, so it depends a lot on the amount of goods available, and you may have to adjust the prices according to supply and demand in order for the freighters to work properly.

[Nebula]

Having a good trading system is important. I was going to make such a system but have delayed it.

I would suggest you check other freighters destinations before sending them out(cheating). You might end up not being able to sell the goods ect. In real life traders sort of know what their competition is doing, so this cheating is not bad. What would be fun is to add trading experience. A unexperienced player would trade badly and have little profit and the experienced player would use the best settings.

I asume your pathing routine knows when paths may be dangerous ect. Freighters could end up being sunk in kill zones.

As for the time it takes for the algorithm to find the best routes, I would suggest storing the data once this is calculated. Then update/evaluate this data with anything you might come up with.

I will add trading in my game when I get a better millitary system. Then I would be able to merge this with the trading system. ea. Have protection for traders, convoys ect..

[Lemmy]

I may be dumb, but I'm not sure I understand exactly what you want so forgive me if that's totally off.
You have ports with freight inside, and freighters which can carry the freight.
For each good, you can compute the best cost you will get for it, by looking at the cost in every port, the difference of costs and then subtracting the distance cost. Since both cost of moving and upkeep cost are linear on distance/time, they are a well-defined unchanging feature of the path used.
Once you've computed that, you have a set of paths, each with a cost/revenue. A freighter would look at the nearest port, look at the best route from that port and choose it.
Better, a freighter would look for the best route in the world, look where the starting port is, then decide to pick the best route from where it is to the starting port of the best route.

That would sorta work, but what i'm worried about is the running time of this algorithm. The prices of goods change all the time and amount of goods for sale can be quite large (several thousands). So for each of these goods, i'd have to check all the places to find a place to sell the good to. this either a lot of administration (keep lists of where each good is sold/bought), or a lot of computation time (check all the places all the time).
Note that the frist method wouldn't necessarily find the max profit routes, and the 2nd method will have to look through all x thousand routes.

The real problem here is not algorithmic but economic: There must be a limited amount of supplies to carry otherwise everyone will trade the same good, so it depends a lot on the amount of goods available, and you may have to adjust the prices according to supply and demand in order for the freighters to work properly.

The actual model is a bit more complex then i stated here. The profit isn't all about currency, but also about trading to places that really need the goods, e.g. trading to places with high priority. I think that by finding the right priority values for the different routes the freighters will be spread out over routes instead of using just a few high currency profit ones.

I would suggest you check other freighters destinations before sending them out(cheating). You might end up not being able to sell the goods ect. In real life traders sort of know what their competition is doing, so this cheating is not bad. What would be fun is to add trading experience. A unexperienced player would trade badly and have little profit and the experienced player would use the best settings.

I agree, cheating in this form is vital.
For example: Suppose you have a freighter with 2 waypoints, x and y. The goods are sold at y and bought at x. The arrival time at x is within 15 days, and it will bring in as many goods as are asked.
Now the next freighter needs to find a route, and it finds that it can buy the same goods at z, and sell them at x but within 10 days.
The first freighter then either needs to cancel its route and find a new one or i twill arrive at x with goods that x doesn't want anymore.

I asume your pathing routine knows when paths may be dangerous ect. Freighters could end up being sunk in kill zones.

As for the time it takes for the algorithm to find the best routes, I would suggest storing the data once this is calculated. Then update/evaluate this data with anything you might come up with.

I will add trading in my game when I get a better millitary system. Then I would be able to merge this with the trading system. ea. Have protection for traders, convoys ect..

Heh, i'm doing it the other way around, first trading, then some kind of military system

And i'll have to think a bit about storing the data...

[LDiCesare]

I'd first code the algorithm and only then make measurements about time taken. Sometimes, actually very often, the time bottlenecks are not where you expect them. Anyway, if you have 1000s of goods, you should probably pick only the most valuable ones. This is how I do things in Clash (it's military ai stuff but basically the same thing):
I have several possible plans, each having a value which is a constant times the target square value divided by a constant + the time to get there. This is very similar to your situation, except I spend lots of time in pathfinding because paths are not constant (varies on unit, built roads, and I think there are many more squares than you would have ports). You can probably avoid computing paths every turn.
What I do is first order the plans, so I know the maximum expected value of a good. Once this is ordered, you can check each good in order, which usually saves 90% of the computation in my case. In your case, ordering would have to be a heuristics, in order to prune the search tree.

If you speak about performance, how many freighters, goods and ports do you expect to have? Also, what is the relative cost of travelling (is it little in comparison with the profits, or is it more important or about the same as the value you can expect from a good)?

[Lemmy]

some estimates:
ports: 200
goods: ~20 per port (buy and sell)
freighters: several per route, but i don't know yet how many routes there would be...maybe 1 per good as an average, and 1 to 10 freighters per route.
The travel costs will generally be smaller then the profit (duh , but high enough to make long distances undesirable.
These are very rough estimates though...i was planning to test bottlenecks with a basic algorithm, but i'd first need the framework finished

The things is, you can't really order the routes based on profit, because the actual profit for a freighter x will be vastly different from the "base profit" based on its location.
The "correct" order of the goods can vary greatly for the different freighters.

I've gotten several ideas now that could provide a (not the) solution, but i'll have to see how the datastructures will end up like.

[skolapper]

Ahh thought it might have been , bit strange though because they were all together in the shop with no chasing. Any idea if it will just stop or will i need to remove him?

[robinp]

I can comment with enthusiasm but no coding expertise on three of the problems mentioned.

On the problem of reaching the source but finding all the goods have been sold:

The online game Ikariam has a market system that involves players making public offers then making contracts with people who respond to the offers, thus theoretically guaranteeing that the ordered goods will be available (and I guess the programmer can ensure that, e.g. by putting those goods in a trust account until collected).

The problem at the other end - recipient having had too many offers and not wanting yours when you deliver. Maybe all movement should be on the basis of contracts agreed as above (between computer-controlled port operators), with the freighter owners bidding to be the chosen carrier for each agreed deal. A freighter owner who sees that he can backload or otherwise combine with another deal will be able to offer a lower price (even if his starting location is some distance away) than one whose freighters cannot combine that deal with any other.

Real problem may be to get a playable game between humans and AIs - the gathering and processing of information would be practically instantaneous for AIs but take minutes or hours for a human, so a real-time game might be unplayable unless the AIs were constrained in some way (e.g. maximum number of contracts per hour). Transport in Ikariam takes minutes or hours, but there are no AIs.

Railroad Tycoon has AIs who have to make decisions about which goods to pick up and transport to wherever, for the greatest net profit per year. But they create their own lines and stations to produce goods from the surrounding tiles, and there's a complex formula that rewards speed more for some goods (notably mail) than others (notably bulk goods - non-perishables - such as coal). The AIs and the human are not in competition for the same batches of goods because they are normally not allowed to have overlapping stations, but, with a numerical limit on the number of trains and the number of stations and a congestion factor that will not allow too many trains at once on one section of track, they do have to make decisions such as "Should my last train be built in Charlottesville and have just one car for speed and take mail to Baltimore or Dover (returning with mail from there), or should it have two or three cars so as to take passengers too (with the added complication that Baltimore produces relatively few passengers, so for speed I might want to drop one car off for the return trip - but dropping a car off takes time!)? Or should I build one at Salisbury with eight cars to shift that coal to Dover and bring steel back? Or should I respond to that priority job that has just been announced and take that food from Baltimore to Winston-Salem with little chance of picking up anything really profitable at the latter when I finish?"

I'm not sure whether the free imitation FreeRails (on SourceForge) has AIs, because in the very few hours I've played with it I've not seen any evidence. Maybe that needs completion by one of you coders with time on your hands?

Sorry I can't start to help with the programming. My expertise reached only as far as Commodore BASIC v 3.5.