15-10-2003 15:42									#1
	Some sort of routing algorithm.. Support Apolyton buy from Amazon

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

	18-10-2003 00:05									#2
	Support Apolyton, buy Civilization: The Boardgame

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.

	18-10-2003 11:45									#3
	Support Apolyton buy from Amazon

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..

	18-10-2003 14:39									#4
	Inflate your Upload Space

quote: 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.

quote: 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.

quote: 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.

quote: 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...

	18-10-2003 17:23									#5
	Suffering from ads?

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)?

	19-10-2003 19:50									#6
	Browse Apolyton AD-FREE

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.