PSPx форум - Кротчайший путь для поиска кораблей и тотальное уничтожение

PSPx форум (https://www.pspx.ru/forum/index.php)

- Программирование для PSP (https://www.pspx.ru/forum/forumdisplay.php?f=101)

- - Кротчайший путь для поиска кораблей и тотальное уничтожение (https://www.pspx.ru/forum/showthread.php?t=19465)

mushue

03.10.2006 16:12

Кротчайший путь для поиска кораблей и тотальное уничтожение

Сегодня узнал о том, что pspowner программирует "Морской бой" как сингл, тоесть для одного игрока, а в роли другого учавствует AI (тоесть искусственный интелект ЗЫЗы :) )

Желаем удачи pspowner'у !

И вот какую тему хотелось бы затронуть: "Кротчайший путь для поиска кораблей и тотальное уничтожение"

У нас имеется матрица 10х10 (ну это для примера). В неизвестных, для нас и AI, точках находятся корабли 1-4 палуб. Мы знаем, что корабли не могут соприкосаться друг с другом, минимальный интервал между бортами двух кораблей - одна клетка.

Какой механизм поиска верного пути вы бы предложили попадая с первого выстрела во вражеский корабль (если он не однопалубный) ?

добавлено через 41 минуту
Я бы предложил следующее:

Оганизуем структуру:

Код:

 

typedef struct  _war_ {

       int x;  // координаты точки поражения

       int y;

       int direction; //направление удара

       int count;   //подсчитаем кол-во палуб

} sea_war;

 

sea_war target;

После этого начинаем палить. Для начала мы палим по рандомной точке:

target.x = 10;
target.y = 10;
target.direction = 0;
target.count = 0;

Если target.direction нулевой, то продолжаем определять другую координату для стрельбы (это может быть простым рандомом)
И вот, при очередной стрельбе мы попадаем. Если корабль 1 балуба. убили его. Если не убит то нацеливаемся дальше.

Нацелить можно по следующей схеме:

Код:

    if (target.direction == 1 )  target.next.x++;

    if (target.direction == 2 )  target.next.x--;

    if (target.direction == 3 )  target.next.y++;

    if (target.direction == 4 )  target.next.y--;

target.direction достаточно инкреиментировать или декрементировать, чтобы выбрать другой путь при ошибочном направлении от предыдущего выстрела.
Если на пути target.direction встречается промах, а target.count > 2, то нам достаточно инвентировать target.direction и откатить координату на target.count, что бы продолжить в другом направлении от начальной точки выстрела.

Вот вобщем-то и всё!

pspowner

03.10.2006 20:17

Я сегодня утром успел только, пока не припахали, написать начало графики. Даже полной расстановки кораблей пока нет. И нужно избавиться от мелких багов и упорядочить текст, а то каша пока :)

добавлено через 52 минуты
Да, вот чё хотел спросить: ReadBufferPositive - у меня гадина отрабатывает по 5 раз на нажатие(ну в цикле когда), приходится лепить холостые циклы. Обнуление Buttons ничего не даёт. SamplingCycle(1) - я так понимаю что-то вроде typematic rate - помогает на 1.5, а как делать на 2.71-2.80? Онаж там не размечена...

mushue

04.10.2006 09:17

В своем СДК я определил SamplingCycle, но его работоспособность не проверял.
В своих программах я использовал простейший путь решения проблемы:

Код:

int i;

while(1){

 if ((i % 10) == 0) {

    //тут обрабатываем кнопки

}

i++;

}

Смысл именно модульности. Тоесть i по модулю 10. Клава обрабатывается каждый 10 тиков.

pspowner

04.10.2006 10:34

Сейчас уже разобрался со случайными числами, почти...
Во первых, имперически выяснил, что int rand(), не возвращает отрицательных значений. Соответственно, возможный диапазон 0-32767.

Собственно, случайное расположение кораблей ЦПУ я делаю примерно так:

Код:

int Randomize9() { 

int r=rand();

if (r>0 && r<=3500) r=1;

if (r>3500 && r<=7000) r=2;

if (r>7000 && r<=10500) r=3;

if (r>10500 && r<=14000) r=4;

if (r>14000 && r<=17500) r=5;

if (r>17500 && r<=21000) r=6;

if (r>21000 && r<=24500) r=7;

if (r>24500 && r<=28000) r=8;

if (r>28000 && r<=31500) r=9;

if (r>31500) r=0;

return r;

}





int ThrowCoin() {

int r=rand();

if (r>16383) return 1; else return 0;

}



void DefineCPUShips() {

int cntx, cnty;

int px,py, cnt;

int isOK=0;

int deck=4, Left=1; 

int direction=0;

while (!isOK) {

px=Randomize9();

py=Randomize9();

direction=ThrowCoin();

if (!direction && px<=6 || direction && py<=6) isOK=1;

}

for (cnt=0; cnt<3; cnt++) if (!direction) fieldCPU[px+cnt][py]=1; 

                                else fieldCPU[px][py+cnt]=1;

RepaintGrid(CPU);

}

mushue

04.10.2006 10:47

Если ты не будешь инициализировать генератор случайного числа то по дефолту srand(1), это значит, что твои корабли все время буду выстраиваться в одну и туже позицию. =)

Что бы этого избежать иницализируй генератор вот таким образом: srand(time(0))

Для низиализации r используй простую вещь как return (rand() % 9)
В ThrowCoin() тоже самое return (rand() % 1)

pspowner

04.10.2006 10:53

Цитата:

Сообщение от mushue (Сообщение 212890)

Если ты не будешь инициализировать генератор случайного числа то по дефолту srand(1), это значит, что твои корабли все время буду выстраиваться в одну и туже позицию. =)

Как ни странно, этого не происходит. При повторном запуске, караблик уже в другом месте :) Кроме того, srand() опять таки не присутсвует в tiffsdk.

Цитата:

Сообщение от mushue (Сообщение 212890)

Для низиализации r используй простую вещь как return (rand() % 9)
В ThrowCoin() тоже самое return (rand() % 1)

Мда, так проще. Спасиб :)

mushue

04.10.2006 12:25

Насчет rand() конечно мне не понятно, ведь поидеи нужно сначало инициализировать генератор, возможно это уже реализовано автоматически.

добавлено через 1 час 7 минут

Код:

void DefineCPUShips() { Как я понимаю, то это функция расставляет кораблики

int cntx, cnty; 

int px,py, cnt;

int isOK=0;

int deck=4, Left=1; 

int direction=0;

while (!isOK) {

px=Randomize9();

py=Randomize9();

direction=ThrowCoin(); <-- тут получаем направление 

if (!direction && px<=6 || direction && py<=6) isOK=1; <-- Это вообще сомнительно всё.  А если этому условию не будет соответствовать примерно n-ое кол-во раз? Как я понял ты старался сделать условия так, чтобы при генерации корабля, он не выпал за рамки самого поля.

}

for (cnt=0; cnt<3; cnt++)  <-- Ясное дело заполняем поле, но почему 3-х палубным корабликом?

        if (!direction) fieldCPU[px+cnt][py]=1; 

          else fieldCPU[px][py+cnt]=1;

RepaintGrid(CPU);

}

Я бы сделал это при помощи рекурсивной функции.

pspowner

04.10.2006 12:37

Код:

void DefineCPUShips() { Как я понимаю, то это функция расставляет кораблики

Это прототип, уже выглядит подругому.

Код:

if (!direction && px<=6 || direction && py<=6) isOK=1; <-- Это вообще сомнительно всё.  А если этому условию не будет соответствовать примерно n-ое кол-во раз? Как я понял ты старался сделать условия так, чтобы при генерации корабля, он не выпал за рамки самого поля.

А пофиг сколько не соответствует, будет кидать случайные числа пока не попадёт куда надо. Добавил ещё ИФов - , конечно, выглядит зловеще.

Код:

<-- Ясное дело заполняем поле, но почему 3-х палубным корабликом?

Ну что ты цепляешься к пустякам :) там >= для 4 палубного. Этож не дописано ещё :)

Цитата:

Я бы сделал это при помощи рекурсивной функции.

Э?

mushue

04.10.2006 12:44

Цитата:

Сообщение от pspowner

Э?

Прости что так критично.. больше небуду =)

Да, рекурсия простой способ получить нужный результат. Ну например:

Код:

int SetOneShip(int x, int y) {

   if (fieldCPU[x][y] > 0 ) return SetOneShip(Randomize9(),Randomize9());

   fieldCPU[x][y] = 1;

   return 0;

}

Данная функция пытается поставить однопалубный кораблик в то место где еще не занято и будет это делать до тех пор пока не поставит =)
Для многопалубных рекурсия немного сложнее.

pspowner

04.10.2006 12:50

Да ничё, я ж не профи. Меня критиковать можно...
Спасиб, но я уже так расставил :) по своему.

Когда закончу, пришлю те исходник. Для критики :)

mushue

04.10.2006 12:52

Цитата:

Сообщение от pspowner (Сообщение 212927)

Я стараюсь всегда оптимизировать, незнаю.. иногда это бывает лишним, но моя натура такая =)

Исходник конечно ждём =) Ох, я в предвкушении критики =)))))

pspowner

04.10.2006 13:37

Ню вот, с расстановкой кораблей я вроде закончил :)
(слева - расставил я в запущенной программе. справа - ЗЫЗа, САМА!)
По крайней мере 2 раза подряд никаких багов в расстановке нет.
Теперича переходим к самому интересному - стрельбе :)

http://g.foto.radikal.ru/0610/4bf8d43c5fc5.jpg

mushue

04.10.2006 13:47

Цитата:

Сообщение от pspowner (Сообщение 212949)

Зергуд. Выглядит неплохо =)

pspowner

04.10.2006 16:31

Ну вот, собственно. Ранняя бета (не релиз, просто для показа). Не распространяйте на форуме - пока не дописано.

Ограничения:

- Пользователь сам отвечает за корректную расстановку своих кораблей.

- Логика стрельбы ПСП пока не написана(т.е. никаких добиваний).
Палит наугад.
- Убитые/раненые не обозначаются.

- Могут быть баги...

Управление:

Стрелки - (движение кораблей при расстановке, движение целеуказателя)
R - Поворот корабля при расстановке
Крест - Выстрел.

Start - выход

Select - Чит. Показывает корабли врага.

2.71 - Работает, 2.80 - Должна :)

vAST	04.10.2006 16:33

оффтоп - о, смотрю и вложениями начали пользоваться

vAST	04.10.2006 16:34

а зачем ты все время лоадбинари в корень ФОТО бросаешь? сделай для удобства как мишуе

pspowner

04.10.2006 16:38

Ну а как? Могу запихнуть в туже папку что и seafight... Сейчас сделать?

Да, сегодня уже врятли буду доделывать - устал :)

vAST	04.10.2006 16:40

запихни или если это можно и мне сделать то лучше я сам, по дороге домой потестю

mushue

04.10.2006 16:47

Браво!!! Работает прекрасно. Багов пока не увидел, есть только недоделки =)

pspowner

04.10.2006 16:48

Что-то я не понял... Запихиваю в туже папку - виснет. Mushue, как это правильно делать не подскажешь?
Я имею в виду как лучше по папкам пихать.

2вАСТ: Если сам будешь править, название проги находится в loadbinary.tiff по смещению 0DBA (если понадобится)

mushue

04.10.2006 17:05

запихнул как есть перенес тифф файл в туже папку, на всяк случай кинул туда имидж.. и всё стартую папку кнопкой X

pspowner

05.10.2006 12:25

Короче, я отложил написание. Туплю чего-то.

Муш, если чего - исходник прилагаю.

mushue

05.10.2006 14:03

сохранил на флэшку, дома гляну..

pspowner

20.10.2006 10:12

Вобщем ничего я пока не пишу. Нет вдохновения, да и писать особо нечего.
Для 1.5 всё что можно написано, а для 2.8 - ??? Да что там можно написать? Вся надежда на еЛоадер, а фанжита молчит. Видать SCE наколбасила реальную защиту.

По поводу ООП: Оказывается, я не тот файл компилил :slow:
Классы действительно не катят, причём даже в 1.5 СДК. (может нужны какие-нибудь доп директивы. в makefile?) Делать через struct тоже не выходит.

МБ - пока в свободном плавании. Мне надо просто заставить себя сесть за дописание.

З.Ы. Кстати, а куда пропал vAST? Давно не видел на форуме... Надеюсь что случилось лучшее ;)

mushue

20.10.2006 10:23

Цитата:

Сообщение от pspowner (Сообщение 225771)

Ограниченные возможности программирования на ТИФФ сдк побудили меня тормазнуться в этом деле. Конечно я елоадера особо не жду, но и его наличие не помешает.
Никакие директивы не нужны, смена компилятора должна быть =) Я менял компилятор, но в случае с ТИФФ сдк это не катит.
вАСТ в отпуске, причем он там уже с понедельника. На сколько отпуск у него я незнаю, но в любом случае минимум 2 недели. Он таакже ожидает рождение ребенка. Я думаю, что вАСТу некоторое время будет не до форума. =)

pspowner

20.10.2006 10:51

Ты извини за назойливость, а на какой компилятор надо поменять?
Просто сейчас самому искать неохота. psp-cpp.exe?

mushue

20.10.2006 10:55

Цитата:

Сообщение от pspowner (Сообщение 225795)

Ты извини за назойливость, а на какой компилятор надо поменять?
Просто сейчас самому искать неохота. psp-cpp.exe?

=)
psp-cpp, psp-c++, psp-g++, psp-gcc

pspowner

20.10.2006 11:51

Гы... ЛОЛ

Муш, забавно. Всё это делается банальной сменой расширения .c на .cpp :)

Да, что-то я :slow: сегодня

Уже накатал для проверки классов прогу. Всё компилится на ура.

Темный_Хамяк

02.12.2006 01:07

Ребята обьясните чё и где писать а то ничё не помню

pspowner

02.12.2006 02:09

Цитата:

Сообщение от Dandj (Сообщение 266407)

Ребята обьясните чё и где писать а то ничё не помню

Я извиняюсь, а Вы кто? Я в смысле... каким ветром Вас к нам занесло.

SееD	02.12.2006 02:18

это ошибка матрицы, про которую вАСТ у***** забывает уже несколько дней :)

Темный_Хамяк

07.12.2006 13:37

Я разработчик

mushue

08.12.2006 10:07

Цитата:

Сообщение от Dandj (Сообщение 272501)

Я разработчик

Привет, не подскажешь а чего разработал?

Цитата:

Сообщение от Dandj

Ребята обьясните чё и где писать а то ничё не помню

Извини конечно, но "чё" писать - имхо дела каждого, а вот "где" писать - сугубо личное.
Если действительно нужно что-то узнать, то было бы не плохо излагать конкретнее.

Текущее время: 14:30. Часовой пояс GMT +3.