http://www.matrixgames.com/forums/tm.asp?m=3221975
Not posting it here to drum up support for Josh or anything (I strongly advise you just skip over anything posted by Kayoz, don't sink to his level), but I did find Josh's posts in the thread on pages 2-4 to be pretty informative.
He goes into some small depth on his algorithms for AI NPC Pathfinding, Trading, etc.
Anyway, it was some details I hadn't seen posted elsewhere yet.
Here are some choice excerpts:
JoshParnell wrote:As for the Limit Theory AI, it uses an even simpler model for high-level AI, which is nonetheless absurdly powerful. The core of LT AI is a planning engine, in which high-level goals are formulated as game state differentials, and then a set of heuristics is called upon to turn a game state differential into a sequence of concrete actions. For example, an obvious heuristic is that if a goal is to modify the location of oneself, the "solution" is to "travel" to the desired location. It's effortless to think of an AI model in this way, and equally effortless to implement. But I claim that the results are impressive and fast. I guess that's the part that I'll have to prove!
JoshParnell wrote:I understand the "how to fly" might seem like a difficult problem if you haven't implemented it. The truth, however, is that it's fantastically simple. The underlying methodology is that, at all times, you have several AI "substrategies" that get to submit votes on a heading. The votes are aggregated as a weighted average, and the current heading is exponentially smoothed with the new heading, as determined by this aggregation. Now, to determine heading, we have several different types of behaviors. Dodging around obstacles, as you mentioned, is implemented by performing a proximity query on the ship, then selecting an obstacle that is relatively close, choosing a random point on the surface of it's world-space AABB, then voting for a heading in the direction of that point. This provides compelling "dodge-em" mechanics. Trying to hit your flanks, of course, is completely trivial - one sets the heading to point towards the target ship. Or, better yet, a random point on the surface of the target ship's world-space AABB, which provides interesting variation when the target is a large ship. Now, there are also concurrent substrategies submitting votes to achieve obstacle avoidance, or for maintaining a formation, or whatever other behavior you'd like. In either case, I'd be happy to explain to you exactly how the heading is computed if you think it's difficult.
As for trading. Here's a simple model: suppose the NPC has a set of known locations. Randomly select some subset of these locations (for variability). Choose some subset of trade goods (perhaps the NPC deals in a certain type of good; it's trivial to generate such a set). Compute the good with the largest price differential among the locations, or, perhaps, the largest price differential per unit volume (again, it's obviously simple, just an outer loop over goods and an inner loop over locations). Now, invoke a "trade" strategy, where the good is the chosen good with maximal price differential, the "source" is the location with the lowest price, and the destination is the planet with the highest price. Other AI strategies, e.g. "TravelTo" will perform the rest of the work. Of course, this is a very simple algorithm, and the algorithms in LT are more complex. Nonetheless, it is a perfectly valid way to determine "what goods the NPC traders and carrying and to where."
JoshParnell wrote:Sure! These are all great extensions to the basic algorithm! But surely you can see that they're all easy!HanBarca wrote: 1. distance
how much it costs to bring the goods there?
2. risk
Is the source planet safe ? And the destination?
3. Offer
How is the availability of the good on the source planet ? How much is the cost going to increase if other traders buy it ?
4. Demand
How is the demand on the destination planet ? Is the market going to be saturated by excessive offer or by other traders ?
5. Other sources
If the transport costs raise the final price by 30%, would the NPC goods be more expensive than the same item taken from a source nearer and maybe unaccesible to the NPC?
I'm not saying the above points aren't manageable, but even the basic economic model looks to me a little more complicated than you think.
What we will want to do is compute, instead of maximal price differential, maximal "appeal" (this is actually what the engine uses at the moment). The appeal is just a function of several variables that outputs a scalar that represents how favorable the trade is. To compute it, we can take all of the above (and more) into account without a problem!
1. Distance
We already have a graph for calculating distance to various destinations, so you can factor this into the appeal function. Note that we will actually compute travel time, not distance, because that's what matters (but that's also what the pathfinding graph already considers). So we will divide the "appeal" equation by this travel time, so as to turn the computation into a computation of "value per unit time spent on the trade."
2. Risk
Sure! We take the NPC's faction, and look up the source and destination planets' factional disposition towards the NPC's faction. We can, for example, factor this in by multiplying by 1-e^(-k*disposition), where 0 means worst possible disposition, hence, this component will be zero (we never go there), and infinity means best possible disposition, hence, we have no qualms about going to this planet. If the NPC is not associated with a faction, we can do something simpler like take the security rating of the system that the planets lie in.
3. Offer
I contend that this isn't really a factor, since the price will already reflect this.
4. Demand
Again, I contend that it isn't a factor, because the price already reflects it.
5. Other Sources
It's actually an emergent property of the algorithm we've already discussed, not a special case. If we factor in distance, as we did above, then NPCs will be less likely to make a long-distance trade. That means that, if the only source of some good is far away, the supply will be thinner, hence the price higher. So yes, if the player (or an NPC) finds a new source of the good that is closer, they will be in good shape to make a profit! That's part of what makes exploration so appealing. And I think this is a very desirable property (it's no different from real life).
One thing that I want to point out is that, often, implementing the right features results in the emergence of other features. We could probably find a bunch of cool consequences of implementing 1. and 2., but we didn't have to do any extra work to achieve them!
I hope this gives some sense of how easy it is to extend the basic economic model to something complex! If you have other ideas, feel free to throw them out and we can explore the ramifications.
