Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Карта для игры

Автор: arts80 4.5.2006, 13:38

Необходимо реализовать карту для игры. Предполагаемый размер карты 10 000 x 10 000, каждая клетка карты - объект (объекты в игре идентифицируються типом long и храняться в базе данных).

Задача - требуеться минимальное время для определения есть ли в ячейке карты объект и поиск пути между клетками, при условии что некоторые объекты не проходимы. Алгоритм поиска известен, но проблема в организации хранения карт, хранить в виде двумерного массива потребует уж очень много памяти. Кто что посоветует ?

Использовать NIO Mapped Buffer на файл размером 10 гиг - насколько будет быстрая работа с таким файлом ? в основном требуеться READ_ONLY доступ

Автор: sandello 4.5.2006, 14:52

надо ж замыслить такое...
Вопрос: во взаимодействии могут участвовать любые точки на карте?

Автор: ALKS 4.5.2006, 14:52

10 000 x 10 000 x 8 byte (long) это что-то около 800Kb. Разве это много?

Автор: powerOn 4.5.2006, 14:59

Можно поизмываться и хранить данные о наличии объекта ввиде потока битов.
long это 8 байт, т.е. 64 бита - 64 клетки.

1 - есть объект, 0 - нет объекта. Установка и получение значений через побитовые операции.

Автор: arts80 5.5.2006, 05:51

Цитата(ALKS @ 4.5.2006, 14:52)

10 000 x 10 000 x 8 byte (long) это что-то около 800Kb. Разве это много?

10 000 x 10 000 = 100000000 элементов
если по 8 байт то 800000000 байт всего или 762 мегабайта, что вообще уже не мало, а вы как считали ?

Добавлено @ 05:53

Цитата(MoonCat @ 4.5.2006, 14:59)

Да, как вариант для определения пути (свободные или нет клетки) он подходит, но опять же проблема в том что надо знать какой именно объект находиться в клетке

Добавлено @ 05:55

Цитата(sandello @ 4.5.2006, 14:52)

надо ж замыслить такое...
Вопрос: во взаимодействии могут участвовать любые точки на карте?

не любые, вообще когда человек стоит на одной клетке - ему надо переместиться на другую, то есть достаточно обработать квадрат 50x50 при поиске пути, но предполагаеться 1000 - 10000 игроков on-line одновременно, так что быстродействие на первом месте

Автор: ALKS 5.5.2006, 08:16

ой да, насчет объема ошибся, сорри smile

Автор: sandello 6.5.2006, 06:50

Цитата(arts80 @ 5.5.2006, 08:51

)

10 000 x 10 000 = 100000000 элементов
если по 8 байт то 800000000 байт всего или 762 мегабайта, что вообще уже не мало

Тьфу, напугал. Всего-то гиг оперативки... Поставь два и не мучайся :-)

Цитата(arts80 @ 5.5.2006, 08:51

)

предполагаеться 1000 - 10000 игроков on-line одновременно, так что быстродействие на первом месте

Т.е. это сетевая игруха... из разряда mm.. (которые массив мультиплеер). Тогда нечего выдумывать с файлами, можно расчитывать только на оперативку, ибо ни один дисковый своп не будет быстрее оперативной памяти.

Автор: arts80 6.5.2006, 09:12

пришел к этому же решению, поставим гиг 8 и нормально будет

Автор: ALKS 6.5.2006, 10:21

а ваша java машина 8 гиг сможет адресовать? под Windows 2Gb на один процесс максимум. это притом что вы сможете даже 2 Gb отъесть. например заставить java 1.4 захватить 2Gb на машине с 4Gb физической памяти нам так и не удалось.... можно конечно несколько процессов запускать но тут уже понятно все сложнее...

Автор: arts80 6.5.2006, 14:06

будет java1.5 и один из вариантов Linux

Автор: ALKS 6.5.2006, 14:33

Цитата(arts80 @ 6.5.2006, 14:06)

будет java1.5 и один из вариантов Linux

эм... а Linux 64bit ? 2GB это не с потолка взято. это следствие 32 битной адресации. 32я битами можно проадресовать 4096Mb максимум. но в Windows 1 бит зарезервирован для каких-то нужд, вот и получаеться 2048Mb на процесс. и это теоритический максимум для любой 32х битной версии Windows. Linux я не знаю но любая 32х битная OS не может выделить процессу памяти больше чем 4096Mb даже теоритически. но на практике я сомневаюсь что это удасться. Java 1.4 под Windows имеет какие-то глюки и даже 1.5GB захватить не в состоянии... кто сказал что в другой OS будет намного лучше? тестить надо.

с другой стороны с 64bit OS (которой по определению требуются 64bit процессора ) я не сталкивался не слишком-то оно распостранено ещё, да и стоит конкретно...

Автор: JUncle 6.5.2006, 20:11

arts80, я конечно не имею полного представления о вашей задаче, но ИМХО вы используете не тот метод решения.
А для 64-бит ОС надо, сдается мне, и JVM соответствуюшую. Есть ли такие?
Кстати далеко не факт что JVM на один long будет тратить именно 8 байт оперативки (вернее факт, что будет больше).

Автор: ALKS 6.5.2006, 21:03

JVM 1.5 под Solaris SPARC 64-bit и под AMD64 для Windows и Linux точно есть. берите и пользуйтесь.

JUncle, это почему это больше 8 байт на лонг???? а ну-ка отсюда по-подробней пожалуйста.

Автор: JUncle 6.5.2006, 21:52

Накладные расходы на динамическое выделение памяти однако должны быть.

Автор: LSD 7.5.2006, 12:15

Я бы использовал MappedByteBuffer на 64-bit машине с оперативкой не менее 4Гб. Мы не требуем от данных постоянно находится в памяти, но при этом если памяти хватает ОС будет держать эти данные в памяти. И плюс распологать данные в файле так, чтобы соседние ячейки имели близкие адреса, например квадратами 64х64. Для расчета движения вся карта не нужна, а вот соседние ячейки понадобятся.

Автор: regis 10.5.2006, 14:31

Неужели действительно нужна карта ТАКОГО размера?
И насколько она будет заполнена в реальности? Если достаточно редко -- не лучше ли попробовать "разреженную" матрицу для реализации?

Автор: ALKS 10.5.2006, 14:45

вот-вот. смысла резирвировать кучу памяти для зон непроходимых гор и непереплываемых рек. или для зон полностью заполненных однотипным лесом. лучше описывать границы зоны и не каждую клетку. памяти можно здорово съэкономить.

Автор: Stampede 10.5.2006, 22:09

Цитата(LSD @ 7.5.2006, 03:15

)

Я бы использовал MappedByteBuffer на 64-bit машине с оперативкой не менее 4Гб. Мы не требуем от данных постоянно находится в памяти, но при этом если памяти хватает ОС будет держать эти данные в памяти. И плюс распологать данные в файле так, чтобы соседние ячейки имели близкие адреса, например квадратами 64х64. Для расчета движения вся карта не нужна, а вот соседние ячейки понадобятся.

LSD дело говорит. Только я бы маленько развил идею. Тебе нужне абстрагировать представление карты от формата хранения, примерно в виде такого интерфейса:

Код


public interface FieldMap {
  public long get(int x, int y);
  public void set(int x, int y, long val);
}

А потом написать, скажем, файловую реализацию:

Код


public class FileFieldMap implements FieldMap {
  private String fileName;

  public FileFieldMap(String fname) {
    fileName = fname;
  }

  public long get(int x, int y)  {
    Block block = getBlock(x, y);
    return block.get(x, y);
  }

  public Block getBlock(int x, int y) {
    // тут ты вычисляешь номер блока, которому принадлежит точка,
    // смотришь, нет ли данного блока в кэше (типа LRU), подгружаешь
    // при необходимости с диска (вычисляешь физическое смещение в файле)
    // и возвращаешь готовый объект типа Block - описатель квадратной
    // области карты
  }
}

Если сделаешь такую штуку, да экспериментальным путем подберешь оптимальные размеры блоков и размер кэша блоков - то у тебя все будет летать почти так же быстро, как если бы ты все хозяйство держал в памяти.

А после этого можешь над всем этим сделать надстройку в виде описателей зон произвольной формы, что предлагал ALKS. Но сначала - поточечный интерфейс к физической среде хранения. Тогда уже будешь чувствовать себя как в танке smile

Автор: arts80 12.5.2006, 10:28

спасибо, буду рассматривать каждый вариант отдельно, что потому получиться покажу :_)