Just curious, O(1)?

[toqueteos]

Unless you have discovered something new, you have to iterate all ships at least once. Something in my guts tells me once is a bit low no matter how probabilistic this is.

So what is actually O(1) compared to all other battle sims?

[toqueteos]

Example: This https://github.com/jstar88/opbe/blob/master/combatObject/Fire.php#L158 doesn't seem O(1) at all. It's O(n) no matter how hard you try.

[jstar88]

The combat engine compute size is n, a variable counting the amount of ships. Standard combat engines are O(n^2) because there is an iteration over all enemy ships for each your ship.

As you can see from the code, the iteration run on each ship TYPE group, not in EVERY ships in them. Since the ships types are limited,the problem is O(1). It's not possible build an O(1) engine without probability theorems

[toqueteos]

defenderFleet looked like a list of all ships instead of a collection of (ship, count). My bad.

Is this approach suitable for games like the old XWars?

[jstar88]

i dont know what game it is. Anyway it's a general approach :)

[toqueteos]

XWars was the successor of Ogame by GameForge but it didn't turn out as well as they expected so they killed it. It was active a year or so. Ships were customizable by players instead of premade.

[jstar88]

if there are infinite combinations of customization, then the ship types amount is not costant. For example: if a player has 100 ships and 1 ship of each type, then he has 100 ship types.(worst case) But he could has only one ship type containing 100 same ships.(best case) Generally we can say that in a game like that: -standard battle engine is Θ(n_n) because has quadratic complexity in every case; -OPBE is O(n_n): Θ(1) in best case and Θ(n*n) in worst.

if you want implement opbe for xwars, you should make a key ID for every ship type: since they are unlimited you can use ID = md5(sum(ship_params))