Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
1

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

29.07.2014, 13:53. Показов 877. Ответов 11
Метки нет (Все метки)

Вобщем, такая тема:

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

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

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

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

Добавлено через 2 минуты
забыл дописать, что в массиве исходных чисел еще есть числа 7 - нормальная "земля", по которой ходит игрок..
противник стоит на месте.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.07.2014, 13:53
Ответы с готовыми решениями:

Алгоритм обхода поля кубиком
народ - никому не попадалась задачка такого вида: есть поле n*n - начало в координате 0*0(верхний...

Нужен алгоритм обхода БД
Доброго времени! Подскажите пожалуйста, как можно пройтись по всем записям(строкам) таблицы как по...

Алгоритм обхода лабиринта
Помогите реализовать алгоритм обхода лабиринта, на примере матрицы nxn, где 1 (единицы) это...

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

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
11
867 / 717 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
29.07.2014, 15:52 2
alexmay,
Примите за вес "дырки" и черного ящика бесконечность, красного и зеленого ящика -1, и ищите кратчайший путь.
1
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 16:12  [ТС] 3
Это понятно, но все не так просто, как кажется.
Расположение игрока и противника может быть совсем рядом и, если я буду просто искать кратчайший путь, то не наберу нужного количества здоровъя и защиты, чтобы победить в схватке..
0
Почетный модератор
Эксперт С++
5842 / 2851 / 390
Регистрация: 01.11.2011
Сообщений: 6,903
29.07.2014, 16:24 4
alexmay, перебирайте пути по кратчайтости пока не наберете нужного количества ящиков.
1
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 16:42  [ТС] 5
SatanaXIII,
так а как начать идти?
ведь есть ящики, которые, мягко говоря, не желательны( -здоровъе )..
и если я буду таким образом перебирать,то попаду в точку сражения все равно без необходимых ящиков и проиграю.
0
867 / 717 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
29.07.2014, 16:53 6
alexmay,
пометьте ящики с -здоровье, бесконечностью, или лучше кол-во здоровья которое отбирают +1,так вы на них попадете в крайнем случае
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
29.07.2014, 16:56 7
кто понял задачу, скажите, сколько должно быть здоровья и защиты в конце? можно ли ходить 2 раза по одной клетке?
0
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 17:32  [ТС] 8
например, в игрока 1% зд
в противника 100%.
При попадании на ящик со здоровьем - +10% к текущему

Ходить по одной клетке можно много раз
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
29.07.2014, 17:37 9
цель прйити в клетку с противником с наибольшим количеством здоровья?
0
0 / 0 / 0
Регистрация: 29.07.2014
Сообщений: 22
29.07.2014, 18:35  [ТС] 10
SlavaSSU,
не обязательно с наибольшим. просто с бОльшим, нежели в противника.
но тут еще есть один минус: защита тоже необходима, т.к наносимый урон после каждого удара противника в разы больше от начального значения защиты игрока. о защите тоже не стоит забывать.
0
Почетный модератор
Эксперт С++
5842 / 2851 / 390
Регистрация: 01.11.2011
Сообщений: 6,903
30.07.2014, 08:46 11
Цитата Сообщение от alexmay Посмотреть сообщение
защита тоже необходима, т.к наносимый урон после каждого удара противника в разы больше от начального значения защиты игрока. о защите тоже не стоит забывать.
Как можно четче попробуйте расписать сколько чего вообще необходимо, что от этого изменится, что с чем как взаимодействует и на чем отражается. А-то откуда мы знаем все вот эти тонкости? Табличку составьте.

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

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

ок.

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

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


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

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

Добавлено через 5 минут
ходить дальше после того как вы пришли в клетку в противником, уже нельзя. будете драться с тем количеством здоровъя и защиты, с которым пришли. так что все обойти необходимо до прихода к противнику( если будет стоять на самом начале игры, его нужно обойти, чтобы добрать нужные ящики..
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.07.2014, 16:36

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Алгоритм обхода бинарного дерева
Помогите, пожалуйста, составить алгоритм. Есть список (list), который описывает бинарное дерево...

Алгоритм обхода графов в ширину
Написать программу на языке Паскаль алгоритма обхода графов в ширину и описание если не трудно

Подскажите алгоритм обхода графа
Всем привет! Подскажите, пожалуйста, какой алгоритм лучше справится с задачей нахождения нескольких...

Возможность обхода поля побывав по 1 разу в клетке
имеется стандартная задача: поле квадрат 7 на 7 в клетку. в каждой клетке можно побывать 1 раз....


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.