Форум программистов, компьютерный форум, киберфорум
Наши страницы
Программирование игр
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
1

Игра лабиринт. ИИ в лабиринте. Как задать лабиринт

21.10.2015, 18:06. Просмотров 1147. Ответов 10
Метки нет (Все метки)

У меня есть следующее задание:
Дано:
- робот
- лабиринт

Задание:
- Нужно реализовать искусственный интеллект для робота, чтобы он умел находить выход в лабиринте

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

Пишу на Java

Вообщем сейчас я хочу сделать следующее: создать массив из стен. А робот с помощью трассировочного луча ищет все точки пересечения, сравнивая расстояния, находит ближайшую точку (1), вместе с ней он получает еще и стену к которой принадлежит эта точка (это упрощение задачи), то есть получает точки начала (0) и конца (2).
Затем он начинает проверять концы, ближайшие они или нет
- если нет, то он берет половинку между (0) и (1) [(1) и (2)]
- иначе, если это края, то выход, а если не края, то увеличиваем
вообщем так получим стенку, затем робот смотрит на (0) и поворачивается + на маленький угол и все повторяется
(Еще проверяет на сколько различны расстояния до точки (0) и до точки (3) = (0) + маленький угол, если расстояния изменилось больше чем диаметр окружности, которой можно описать робота, то там есть проход и он запоминает середину между точкой (0) и (3) точку (4), а также и точки (0) и (3)) и повторяет снова для точки (4) (возможно не только в ней! а в трех точках на отрезке (0) и (3). 1/3 2/3 3/3 примерно так), этот алгоритм для первого анализа, а для последующих робот игнорирует область, что была до этого(он не смотрит дальше (0) и (3))

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

Если во время анализа он найдет стенку выход, то он сразу же побежит к выходу и конец программы.

Вопросы:
- Как задать лабиринт, чтобы оптимизировать алгоритм?

Я хочу задать так
class Wall {
Point a, b;
}
Class Game {
List<Wall> labir;
}
Но мне сказали, что это плохой вариант

- Что можно изменить в алгоритме для оптимизации?
- Что можно почитать, где похожие задачи реализованы?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2015, 18:06
Ответы с готовыми решениями:

Лабиринт на делфи
вообщем я делаю лабиринт и у меня возникли проблемы -при прикосневении картинки с панелью -при...

Как задать лабиринт?
Необходимо решить проблему нахождения выхода из лабиринта используя DFS, а потом используя BFS....

Как сделать ТХТ Карты? Игра Лабиринт
Вот моя прога uses CRT,GraphABC; var ax,ay,vx,vy,bx,by: integer; A: array of char; ...

Игра Лабиринт
Кто-нибудь может помочь написать игру &quot;Лабиринт&quot; на Си? Или может у Вас есть исходники?

Игра лабиринт
using System; using System.Collections.Generic; using System.Linq; using System.Text; ...

10
8Observer8
3128 / 1726 / 309
Регистрация: 05.10.2013
Сообщений: 5,325
Записей в блоге: 97
21.10.2015, 21:11 2
Цитата Сообщение от dikys Посмотреть сообщение
Вообщем сейчас я хочу сделать следующее: создать массив из стен. А робот с помощью трассировочного луча ищет все точки пересечения, сравнивая расстояния, находит ближайшую точку (1), вместе с ней он получает еще и стену к которой принадлежит эта точка (это упрощение задачи), то есть получает точки начала (0) и конца (2).
Я не понял, как работает трассировочный луч по этому описанию. Можно ли изобразить его работу наглядно в виде рисунка?
0
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
22.10.2015, 09:05  [ТС] 3
Перед алгоритмом робота. Просчитывается диаметр окружности которой можно описать лабиринт, затем умножается на 2. Допустим это число Q. Оно записывается в робота.
Затем у робота есть единичный луч(1,0), который понимается как направление взгляда.
И в том алгоритме. Сначала робот смотрит в сторону (1, 0), для трассировки используется луч Q*(1, 0), то есть ищутся пересечения этого луча со стенками лабиринта, выбирается самая ближайшая точка P пересечения. И получается, что зрение робота упирается в точку P, он сфокусировался на точку P. А дальше по алгоритму.

Надеюсь я ничего не путаю на счет трассировочного луча.
0
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
22.10.2015, 09:16  [ТС] 4
Вот наглядно я изобразил алгоритм, оранжевый отрезок, это проход.

Начинаем с Q*(1,0) далее против часовой. Я там не закончил дальше 270 градусов....
0
Миниатюры
Игра лабиринт. ИИ в лабиринте. Как задать лабиринт  
22.10.2015, 09:16
MELkey
73 / 73 / 13
Регистрация: 15.01.2013
Сообщений: 284
23.10.2015, 00:10 5
хз, насквозь видеть стены это норм для лабиринта?
0
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
23.10.2015, 08:50  [ТС] 6
Робот не видит на сквозь, он смотрит куда-то и функция отвеч. за имитацию зрения возвращает ему точку, на которую смотрит, а эта функция уже использует трассировочный луч для нахождения этой точки, вот она бъет на сквозь все стены, но робот понятие об этом не имеет. Если вам не нравится, то может быть у вас есть другая идея, как имитировать зрения в программирование?
0
8Observer8
3128 / 1726 / 309
Регистрация: 05.10.2013
Сообщений: 5,325
Записей в блоге: 97
23.10.2015, 10:37 7
Цитата Сообщение от dikys Посмотреть сообщение
- робот для изучения геометрии лабиринта может использовать лишь трассировочный луч
Почему-то я не могу найти гуглом метод изучения геометрии лабиринта с помощью трассировочного луча.

Цитата Сообщение от dikys Посмотреть сообщение
он смотрит куда-то и функция отвеч. за имитацию зрения возвращает ему точку, на которую смотрит, а эта функция уже использует трассировочный луч для нахождения этой точки, вот она бъет на сквозь все стены
Можно ли сказать, что эту функцию можно представить, как датчик, который висит на стене?

Добавлено через 2 минуты
Или даже не датчик, а такие картинки, где на белом фоне квадрат и в нём много квадратиков. Забыл как называется. Как?

Добавлено через 11 минут
Это называется QR код.

Цитата Сообщение от dikys Посмотреть сообщение
как имитировать зрения в программирование?
Мой вариант это на концах стен, которые заданы двумя точками, поместить некие объекты, которые знают информацию о лабиринте. Робот этой информации не знает. Он поворачивается и сканирует трассировочным лучом. Если этот луч наталкивается на такой объект, то он узнаёт необходимую информацию и принимает решения. Условия же не нарушаются?
0
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
23.10.2015, 21:44  [ТС] 8
Я бы не писал сюда, если бы вы смогли найти это. Это плохой вариант... датчик наоборот находится на роботе. Например эхолокация, или компьютерное зрение (там примерно похожий результат). Представте лабиринт, у которого на углу стен висит карта лабиринта. Ну бред не?
А почему трассировочный луч, я уже много с кем общался. Это почти не единственный вариант, который предлагали мне остальные, и о котором я сразу додумался, при таком построении лабиринта, что стена это 2 точки.

При использовании трас. луча я перебираю абсолютно все стены. Но походу это не самый эффективный вариант. Мне предлагали поискать то, как задать лабиринт, чтобы не нужно было все проверять, но тогда сущ. какая-то функция, которая контролирует построение лабиринта, а значит скорость работы построения лабиринта из стен + трассировка, которая все стены не рассматривает < скорость трассировки на обычном массиве стен.
0
8Observer8
3128 / 1726 / 309
Регистрация: 05.10.2013
Сообщений: 5,325
Записей в блоге: 97
23.10.2015, 21:58 9
Цитата Сообщение от dikys Посмотреть сообщение
эта функция уже использует трассировочный луч для нахождения этой точки, вот она бъет на сквозь все стены
Я не понял, кто бьёт сквозь стены?

Добавлено через 1 минуту
Цитата Сообщение от dikys Посмотреть сообщение
Представте лабиринт, у которого на углу стен висит карта лабиринта. Ну бред не?
Я имел виду не карту, а некоторые подсказки роботу, чтобы заменить "ту функцию, которая бьёт сквозь стены"
0
MELkey
73 / 73 / 13
Регистрация: 15.01.2013
Сообщений: 284
24.10.2015, 10:38 10
Значит так, как пройти лабиринт?, идти по одной стороне, сторону определяем трасером, тамже определяем где она кончается - точка А1, идём к это точке А1, начинаем трасировать из точки А1, сторона опять кончается в точке А2 идём туда и т.д., если лабиринт монолит то робот выйдет, если из составных частей, то ту часть вокруг которой он уже прошёл просто блокируем для трасировки и в конечном итоге он выйдет из лабиринта, нсквозь бить стены ненужно
1
dikys
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 6
24.10.2015, 16:56  [ТС] 11
Все понятно короче
0
24.10.2015, 16:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2015, 16:56

Игра 'Лабиринт'
Привет всем , собсно тема курсовой работы звучит как &quot;Игровое приложение лабиринт&quot; . Нашёл...

Игра лабиринт VB
Хочу сделать игру типа лабиринта. В которой объект передвигается по полю при нажатии...

Игра Лабиринт
В лабиринте средством перемещения так сказать &quot;персонажа&quot; являются стрелки.Помогите пожалуйста...


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

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

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