Vamos começar com uma imagem:
Atualmente estou fazendo um jogo de estratégia baseado em turnos ambientado no espaço onde você pode estabelecer colônias e transferir minerais das colônias (“foo”, “bar”, “baz” e “qux” na imagem) de volta para o capital (“destino” na imagem). Todo transporte é representado abstratamente por números:
- Star é a capital e o destino de todos os minerais.
- Os círculos são colônias (“nós”).
- Linhas são conexões entre colônias.
- Os números azuis dentro dos círculos indicam quantos minerais cada colônia produz a cada turno.
- Os números verdes próximos às linhas representam a capacidade máxima para essa conexão.
O problema que estou tendo é criar um algoritmo que consiga distribuir adequadamente os minerais produzidos entre as conexões de forma que o número máximo de minerais chegue à capital. Meu algoritmo atual é muito ingênuo e se depara com o seguinte cenário:
- foo quer transferir seus 3 minerais. Como ambas as conexões (foo <==> baz e foo <==> qux) são ambos capazes de transferir 3 minerais, um é escolhido aleatoriamente, neste caso o foo <==> qux conexão é escolhida.
- bar quer transferir seus 3 minerais. Ele os transfere para qx através dessa conexão.
- qx agora tem 7 minerais (1 inicial + 3 de foo + 3 de bar). Desde o qux <==> destino conexão só pode lidar com 4 minerais, ela transfere apenas 4 minerais, deixando 3 presos qx. Observe que ele não pode transferir esses minerais restantes de volta para foo desde a conexão foo <==> qux já transportou sua capacidade máxima de 3 minerais na etapa 1!
No entanto, como podemos ver na imagem, na etapa 1 (foo <==> qux transferência) se foo optou por se transferir para baz em vez disso, não teríamos sobrado 3 minerais na etapa 3. Foi aqui também que encontrei um obstáculo, não consigo criar um algoritmo que possa distribuir adequadamente os minerais de tal forma que nenhum mineral fique “preso “. Consegui criar um algoritmo que pode aplicar força bruta em cada conexão, mas esse algoritmo é brutalmente lento, pois meu jogo pode ter mais de 100 nós com aproximadamente 6 conexões cada.
Tentei pensar nesta solução como um problema de pathfinding (“pessoas tentando chegar a um destino, mas as estradas só suportam um certo número de pessoas”). Sinto que outra pessoa deveria ter tido esse problema, mas infelizmente não consigo encontrar nenhuma literatura nem mencionar esse problema reformulado!
Alguém tem alguma ideia de por onde começar?