Path Finder

@Pro100Tom · Регистрация: 29.10.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте! Хочу сделать следующий симулятор: есть ландшафт, строишь дороги (не только с четырьмя направлениями, а таким образом что сам можешь контроллировать угол, причем хотелось бы еще реализовать дорогу в виде кривой) необязательно, чтобы красиво выглядело. Задача состоит в том, чтобы создать Path Finder, который будет находить наикратчайший путь от одного места до другого. На чем писать, не знаю. Писал игры на C++, с использование OpenGL, работал с XNA и UDK. На Uniti не работал. Люблю очень C#. Я знаю как реализовать A*, знаю, что есть алгоритмы path smooth, но тут проблема заключается в том, что я дороги хотел бы прокладывать любым образом под любым углом.. Посоветуйте что-нибудь пожалуйста. Заранее спасибо!

@ithyphallic · 17.11.2013, 11:42

Возможно в данном случае A* не очень подойдет, попробуйте почитать про Алгоритм Дейкстры

@Pro100Tom · 23.11.2013, 19:04 **[ТС]**

Я изучил эти два алгоритма, но мне все равно нужна помощь. Как сделать вот так? http://www.caliper.com/transmodeler/ Не обязательно так мощно, конечно. Например, как сделать так, чтобы по нарисованной дороге объект (машина) знал, как именно надо ехать (вдоль, например). Как указать ей путь? На чем вообще удобнее такое писать? Win GDI подходит или лучше брать 3Д? OpenGL с C++ там или UDK, Unity...

Добавлено через 8 минут
Давайте так: как нарисовать просто черные линии на белом фоне, создать красную жирную точку и заставить ее двигаться от одной точки до другой по этим линиям как вот тут: http://www.youtube.com/watch?v=1BXtr-3R_4o

@ithyphallic · 24.11.2013, 11:33

Недавно сталкивался с похожей проблемой. Нужно было провести ломаную линию 'уровень земли' состоящую из множества отрезков (пробую делать игру). Когда давно делал такое на Visual Basic - там был класс наряду с картинками и кнопками, назывался отрезок. Задаешь ему x1, y1, x2, y2 - и он на форме. Точно также можно менять по ходу выполнения программы, очень удобно.
Сейчас пробовал делать тоже самое на C++ Builder - тут такого класса нет. Спрашивал на форуме, фактически единственный вариант - рисовать на канве. В данном случае это гораздо менее удобно, хотя возможно сделать. Вот тут можно почитать.

Точку лучше сделать как TImage, загрузив в нее изображение 1 на 1 пикселя. Движение будет задаваться как-то вроде такого:

C++
1
2
3
4
int speed = 5; ///скорость автомобиля
int side = 40; ///длина проекции дороги
machine->Left = machine->Left + speed * cos (side1 * PI / 180); 
machine->Top = machine->Top + speed * sin (side1 * PI / 180);

Это все очень приблизительно, подробнее можно узнать вот тут

Добавлено через 8 часов 24 минуты
Алгоритм примерно такой будет:

1) Создаем массив, который будет хранить координаты начала (x1, y1) и конца (x2, y2) каждого отрезка дороги;
2) Рисуем отрезок на канве Image1:

C++
1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < roadcount-1; i++) /// roadcount - общее количество отрезков дорог
{
Image1->Canvas->MoveTo(x1,y1);
Image1->Canvas->LineTo(x2,y2);
way1x = x2 - x1; /// находим длину проекции отрезка на x
way1y = y2 - y1; /// находим длину проекции отрезка на y
way1 = извлекаем корень из (way1x * way1x) + (way1y * way1y) /// не помню как корень выглядит в c++
/// то есть мы находим длину отрезка (квадрат гипотенузы равен сумме квадратов катетов)
way1cos = way1y / way1; /// коэффициент, который нам необходим чтобы правильно задать скорость изменения координаты по осям таким образом, чтобы точка двигалась строго по отрезку
way1sin = way1x / way1;
}

3) Загружаем точку в картинку machine. Выставляем ее в начальную позицию (например x1, y1 отрезка1).

C++
1
2
machine->Left = x1;
machine->Top=y1;

4) Двигаем ее:

C++
1
2
machine->Left = machine->Left + speed * way1cos;
machine->Top = machine->Top + speed * way1sin;

Не могу сказать что код правильный на 100%, но общий ход должен быть именно такой, без синусов тут точно не обойтись

И в хэдер наверно лучше добавить на всякий случай:

C++
1
2
 #include <math.h>
#include "Math.hpp"

@Pro100Tom · 24.11.2013, 16:23 **[ТС]**

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

@ithyphallic · 24.11.2013, 18:20

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

Или надо кривую указать как кучу прямых коротких отрезков?

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

правда не знаю как это скажется на производительности программы.
Ещё может быть вариант все поле представить как массив пикселей, у каждого из пикселей будет параметр true (является дорогой) или false (не является дорогой), а также цифра, обозначающая его принадлежность к дороге с таким-то номером. А автомобиль будет проверять параметр пикселя который рядом с текущим true или false и в соответствии с этим двигаться либо нет. Но это довольно сложно, я не могу до конца представить как такое делается, но в прицнипе реализуемо.

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@Pro100Tom 154 / 31 / 11 Регистрация: 29.10.2012 Сообщений: 397

	Path Finder 17.11.2013, 01:22. Показов 1309. Ответов 5 Метки нет (Все метки) Здравствуйте! Хочу сделать следующий симулятор: есть ландшафт, строишь дороги (не только с четырьмя направлениями, а таким образом что сам можешь контроллировать угол, причем хотелось бы еще реализовать дорогу в виде кривой) необязательно, чтобы красиво выглядело. Задача состоит в том, чтобы создать Path Finder, который будет находить наикратчайший путь от одного места до другого. На чем писать, не знаю. Писал игры на C++, с использование OpenGL, работал с XNA и UDK. На Uniti не работал. Люблю очень C#. Я знаю как реализовать A*, знаю, что есть алгоритмы path smooth, но тут проблема заключается в том, что я дороги хотел бы прокладывать любым образом под любым углом.. Посоветуйте что-нибудь пожалуйста. Заранее спасибо! 0

@ithyphallic 14 / 14 / 4 Регистрация: 27.10.2012 Сообщений: 141
	17.11.2013, 11:42
	Возможно в данном случае A* не очень подойдет, попробуйте почитать про Алгоритм Дейкстры 1

@Pro100Tom 154 / 31 / 11 Регистрация: 29.10.2012 Сообщений: 397
	23.11.2013, 19:04 [ТС]
	Я изучил эти два алгоритма, но мне все равно нужна помощь. Как сделать вот так? http://www.caliper.com/transmodeler/ Не обязательно так мощно, конечно. Например, как сделать так, чтобы по нарисованной дороге объект (машина) знал, как именно надо ехать (вдоль, например). Как указать ей путь? На чем вообще удобнее такое писать? Win GDI подходит или лучше брать 3Д? OpenGL с C++ там или UDK, Unity... Добавлено через 8 минут Давайте так: как нарисовать просто черные линии на белом фоне, создать красную жирную точку и заставить ее двигаться от одной точки до другой по этим линиям как вот тут: http://www.youtube.com/watch?v=1BXtr-3R_4o 0

@Pro100Tom 154 / 31 / 11 Регистрация: 29.10.2012 Сообщений: 397
	24.11.2013, 16:23 [ТС]
	Спасибо большое. Как это реализовать, если дороги будут под прямым углом еще как-то можно. Но а если дорога кривая, как в России, то как тогда дать понять картинке машины, что надо двигаться по кривой? Или надо кривую указать как кучу прямых коротких отрезков? 0