Path Finder

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

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

Здравствуйте! Хочу сделать следующий симулятор: есть ландшафт, строишь дороги (не только с четырьмя направлениями, а таким образом что сам можешь контроллировать угол, причем хотелось бы еще реализовать дорогу в виде кривой) необязательно, чтобы красиво выглядело. Задача состоит в том, чтобы создать 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++

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++

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 и в соответствии с этим двигаться либо нет. Но это довольно сложно, я не могу до конца представить как такое делается, но в прицнипе реализуемо.

@Pro100Tom 154 / 31 / 11 Регистрация: 29.10.2012 Сообщений: 397
		1
	Path Finder 17.11.2013, 01:22. Показов 1190. Ответов 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	2
	Возможно в данном случае A* не очень подойдет, попробуйте почитать про Алгоритм Дейкстры 1

@Pro100Tom 154 / 31 / 11 Регистрация: 29.10.2012 Сообщений: 397
	23.11.2013, 19:04 [ТС]	3
	Я изучил эти два алгоритма, но мне все равно нужна помощь. Как сделать вот так? 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 [ТС]	5
	Спасибо большое. Как это реализовать, если дороги будут под прямым углом еще как-то можно. Но а если дорога кривая, как в России, то как тогда дать понять картинке машины, что надо двигаться по кривой? Или надо кривую указать как кучу прямых коротких отрезков? 0

@ithyphallic 14 / 14 / 4 Регистрация: 27.10.2012 Сообщений: 141
	24.11.2013, 18:20	6
	Сообщение от Pro100Tom Или надо кривую указать как кучу прямых коротких отрезков? скорее всего да, в принципе отрезки могут быть и по три пикселя длиной правда не знаю как это скажется на производительности программы. Ещё может быть вариант все поле представить как массив пикселей, у каждого из пикселей будет параметр true (является дорогой) или false (не является дорогой), а также цифра, обозначающая его принадлежность к дороге с таким-то номером. А автомобиль будет проверять параметр пикселя который рядом с текущим true или false и в соответствии с этим двигаться либо нет. Но это довольно сложно, я не могу до конца представить как такое делается, но в прицнипе реализуемо. 1