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

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

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

Это сообщение отредактировал(а) arts80 - 4.5.2006, 14:05

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

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

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

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

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

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

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

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

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

Это сообщение отредактировал(а) arts80 - 5.5.2006, 05:56

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

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


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

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

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

будет 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 процессора ) я не сталкивался не слишком-то оно распостранено ещё, да и стоит конкретно... 

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

Это сообщение отредактировал(а) JUncle - 6.5.2006, 20:12

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

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

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

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