Оптимизировать/придумать алгоритм. Просто так.

← →
AV © (2012-09-24 12:30) [0]

Смотрел как играют в одну игру, ради интереса решил подумать вот над чем

Существует игровой мир, на плоскости представляет из себя квадрат, примерно 500х500, но замкнут в 3d.
т.е. пойдя в любом из 8ми направлений(N,NO,..,NW) придешь в эту же точку.
Перемещение по-диагонали нормальное, т.е. по пифагору
Перемещение на 1 клетку = 1 единицы пути и занимает время, примерно, 10 минут.

Мир случайным образом заселен игроками-конкурентами.
Случайным образом по миру распределены генераторы ресурсов, которые медленно производят некоторое их количество.
Генераторы и игроки, после случайного размещения, не меняют своих координат.
Любой игрок видит где все другие игроки разместились и где находятся все генераторы.

Ресурсы могут быть взяты игроком, путем направления им к генератору сборщиков.
Сборщики могут взять из генератора столько ресурсов, каково их(этих самых сборщиков) качество, либо все ресурсы,
если в генераторе их меньше, чем могут взять сборщики.
В генераторе, соответственно, ресурсов не останется.

Игрок имеет первоначальный капитал,
на который он может построить несколько сборщиков ресурсов(3-4 сборщиков),
либо улучшить их качество(возможность брать/переносить больше) (1-2 улучшенных сборщика).
В принципе, ресурсы, потраченные на улучшение в 2 раза одного сборщика, стоят еще одного сборщика.
Большого отличия тут нет, либо строить 2, либо одного навернуть в два раза.

Игрок может знать сколько в каждом генераторе ресурсов, только если он его вычистит под 0.
После того как генератор очищен полностью, следующий посетивший этот генератор сборщик (возможно, другого игрока) ничего не возьмет,
или возьмет 0.0x процента от своей вместимости, если ему повезет, и генератор что-то сгенерирует как раз в этот момент.

Сборщики двигаются от базы (куда игрока случайно забросили) к генератору и назад.
Сборщик не может от генератора посетить другой генератор и дополнить свою вместимость.

На собранные ресурсы сборщиками, можно строить новых сборщиков.
Сборщиков одновременно можно направлять в несколько генераторов сразу.

Задача:
Собрать больше всех ресурсов. Ресурсы, потраченные на сборщиков не отнимаются от результата.

Сразу, возможные проблемы -
1. Наши сборщики ходят по списку. Посещение генераторов получается неудачное,
часто посещаем те, которые уже пусты.

2. Мы видим, что генераторы в 10 часах пути далеко от всех игроков, идем туда, возвращаемся через 20 часов,
хотя могли бы за эти 20 часов обежать все ближайшие 10 раз и если в среднем получаем с них более 10%, то это уже выгоднее.
А если еще с дальних не полными вернулись..

У меня есть идея по решению, связанная с задачей коммивояжера, но хотелось бы послушать как еще можно оптимизировать прибыль :)

← →
Думкин © (2012-09-24 13:16) [1]

> Существует игровой мир, на плоскости представляет из себя
> квадрат, примерно 500х500, но замкнут в 3d.
> т.е. пойдя в любом из 8ми направлений(N,NO,..,NW) придешь
> в эту же точку.

Это тор, бутылка Клейна или что?

← →
КряКря (2012-09-24 13:22) [2]

> Это тор, бутылка Клейна или что?

Это

> TCoord = (0..499);
> ...
> X: TCoord;
> Y: TCoord;

с переполнением.

← →
Думкин © (2012-09-24 13:54) [3]

Значит тор.

Думаю, это тор
крайней точки карты, шаг с доски приведет в точку с противоположного конца

идея два, тупо

копить результаты посещения каждого генератора, вычислять средний "улов",
по максимальным целям ходить чаще.

Отдельно считать цели, когда вернулись со 100%% уловом.
Тут же посылать по таким повторно.

Оптимизировать/придумать алгоритм. Просто так. Найти похожие ветки