Форум программистов, компьютерный форум CyberForum.ru

Составить алгоритм обхода игрового поля - C++

Восстановить пароль Регистрация
 
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 13:53     Составить алгоритм обхода игрового поля #1
Вобщем, такая тема:

Дан двумерный массив чисел 12х12, который содержит числа от 0 до 5.
0 - дырка
1 - мое местоположение( при запуске приложения )
2 - черный ящик( -здоровье )
3 - красный ящик( +здоровье )
4 - зеленый ящик( +защита )
5 - положение противника( противник, как и сам игрок, один ).

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

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

заранее благодарен.

Добавлено через 2 минуты
забыл дописать, что в массиве исходных чисел еще есть числа 7 - нормальная "земля", по которой ходит игрок..
противник стоит на месте.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
XRoy
848 / 698 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
29.07.2014, 15:52     Составить алгоритм обхода игрового поля #2
alexmay,
Примите за вес "дырки" и черного ящика бесконечность, красного и зеленого ящика -1, и ищите кратчайший путь.
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 16:12  [ТС]     Составить алгоритм обхода игрового поля #3
Это понятно, но все не так просто, как кажется.
Расположение игрока и противника может быть совсем рядом и, если я буду просто искать кратчайший путь, то не наберу нужного количества здоровъя и защиты, чтобы победить в схватке..
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
29.07.2014, 16:24     Составить алгоритм обхода игрового поля #4
alexmay, перебирайте пути по кратчайтости пока не наберете нужного количества ящиков.
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 16:42  [ТС]     Составить алгоритм обхода игрового поля #5
SatanaXIII,
так а как начать идти?
ведь есть ящики, которые, мягко говоря, не желательны( -здоровъе )..
и если я буду таким образом перебирать,то попаду в точку сражения все равно без необходимых ящиков и проиграю.
XRoy
848 / 698 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
29.07.2014, 16:53     Составить алгоритм обхода игрового поля #6
alexmay,
пометьте ящики с -здоровье, бесконечностью, или лучше кол-во здоровья которое отбирают +1,так вы на них попадете в крайнем случае
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
29.07.2014, 16:56     Составить алгоритм обхода игрового поля #7
кто понял задачу, скажите, сколько должно быть здоровья и защиты в конце? можно ли ходить 2 раза по одной клетке?
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 17:32  [ТС]     Составить алгоритм обхода игрового поля #8
например, в игрока 1% зд
в противника 100%.
При попадании на ящик со здоровьем - +10% к текущему

Ходить по одной клетке можно много раз
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
29.07.2014, 17:37     Составить алгоритм обхода игрового поля #9
цель прйити в клетку с противником с наибольшим количеством здоровья?
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 18:35  [ТС]     Составить алгоритм обхода игрового поля #10
SlavaSSU,
не обязательно с наибольшим. просто с бОльшим, нежели в противника.
но тут еще есть один минус: защита тоже необходима, т.к наносимый урон после каждого удара противника в разы больше от начального значения защиты игрока. о защите тоже не стоит забывать.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
30.07.2014, 08:46     Составить алгоритм обхода игрового поля #11
Цитата Сообщение от alexmay Посмотреть сообщение
защита тоже необходима, т.к наносимый урон после каждого удара противника в разы больше от начального значения защиты игрока. о защите тоже не стоит забывать.
Как можно четче попробуйте расписать сколько чего вообще необходимо, что от этого изменится, что с чем как взаимодействует и на чем отражается. А-то откуда мы знаем все вот эти тонкости? Табличку составьте.

Что до алгоритма:
1) Найдите кратчайший путь
2) Поглядите хватает ли вам ящиков даже при условии, что будут собраны и негативные, находящиеся на этом пути
3) Если не хватает, то берите следующий по длине путь и переходите к пункту 2.

Но это в лоб.
Волновой алгоритм тут вообще мало пригоден. Вам нужно что-то гораздо умнее. Какой-то рекурсивный волновой (только что придумал термин), который будет мало того находить кратчайший путь, так еще и от каждого шага пути искать ответвления наименьшей длины, но приносящие наибольшее количество плюшек.
К примеру, если можно пройти по прямой до противника, собрав при этом пять полезных ящиков, но отвернув в середине пути под девяносто градусов в бок, пройти пару шагов и собрать шестой, затем вернуться в точку схода с пути и продолжить его будет ли это оптимальнее? Можно ли жертвовать ходами в угоду количества собранных ящиков?
Тут куча тонкостей, которые вы объяснять застрелитесь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2014, 16:36     Составить алгоритм обхода игрового поля
Еще ссылки по теме:

Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего C++
C++ Автоматическое построение игрового поля
C++ Необходимо написать программу обхода конем всего шахматного поля

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
alexmay
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
30.07.2014, 16:36  [ТС]     Составить алгоритм обхода игрового поля #12
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Как можно четче попробуйте расписать сколько чего вообще необходимо, что от этого изменится, что с чем как взаимодействует и на чем отражается. А-то откуда мы знаем все вот эти тонкости? Табличку составьте.
Что до алгоритма:
1) Найдите кратчайший путь
2) Поглядите хватает ли вам ящиков даже при условии, что будут собраны и негативные, находящиеся на этом пути
3) Если не хватает, то берите следующий по длине путь и переходите к пункту 2.
Но это в лоб.
Волновой алгоритм тут вообще мало пригоден. Вам нужно что-то гораздо умнее. Какой-то рекурсивный волновой (только что придумал термин), который будет мало того находить кратчайший путь, так еще и от каждого шага пути искать ответвления наименьшей длины, но приносящие наибольшее количество плюшек.
К примеру, если можно пройти по прямой до противника, собрав при этом пять полезных ящиков, но отвернув в середине пути под девяносто градусов в бок, пройти пару шагов и собрать шестой, затем вернуться в точку схода с пути и продолжить его будет ли это оптимальнее? Можно ли жертвовать ходами в угоду количества собранных ящиков?
Тут куча тонкостей, которые вы объяснять застрелитесь.

ок.

когда игрок приходит в клетку с противником, в фоновом режиме начинается "бой", после которого просто в консоль выводится сообщение кто выиграл.
расчет исхода производится по неким формулам, которые выполняются после каждого ударара...
Урон(игрок) = здоровье( противник ) - защита( противник ) * коэфф.
Урон(противник ) = здоровье( игрок) - защита( игрок) * коэфф.

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


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

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

Добавлено через 5 минут
ходить дальше после того как вы пришли в клетку в противником, уже нельзя. будете драться с тем количеством здоровъя и защиты, с которым пришли. так что все обойти необходимо до прихода к противнику( если будет стоять на самом начале игры, его нужно обойти, чтобы добрать нужные ящики..
Yandex
Объявления
30.07.2014, 16:36     Составить алгоритм обхода игрового поля
Ответ Создать тему
Опции темы

Текущее время: 04:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru