Здравствуйте.
Извиняюсь за Баян, но проблема такова:
Есть поле неизвесных размеров. Есть точка. Необходимо найти путь от точки до неёже самой ОБЯЗАТЕЛЬНО в обход препятствий.
Вся загвоздка в том, что все олгаритмы предодоставляют поиск пути из точки в другую точку, а мне требуется из точки в неёже.


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


Это сообщение отредактировал(а) ano360 - 14.1.2007, 13:05

Если надо через все поле - пробуй генерить где-нить точку(С) в другом конце поля и вызывай два раза поиск пути. сначала поиск(А, С) ты попадешь в точку(С), а потом поиск(С,А) - вернешься обратно.

Не, чаще всего надо будет делать так:

*****************
*****************
*****************
******2**********
*******20********
*****************
*****************
*****************
2-препятствие, которое набо обойти обязательно, хотябы одно.
0-точка начала.
РЕзультат:
*****************
*****************
*****************
******29*********
******920********
*******9*********
*****************
*****************
9-это путь обхода

Или ситуация чуть сложнее:

*****************
*****************
******92**2******
*****929**2******
*****9220**2*****
******99*********
*****************
*****************

Это сообщение отредактировал(а) ano360 - 14.1.2007, 12:46

Путь из точки в точку это путь длины ноль.

И искать его не надо. Это пустой путь

Из точку в точку в обход других.
Те. хотябы одно препятствие должно быть обведено.

Добавлено @ 13:02 
Если есть хоть какиенибудь мысли, даже самые размытые или слишком навороченные,пожалуйста,излагайте, я доработаю сам

Это сообщение отредактировал(а) ano360 - 14.1.2007, 12:49

  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -  -  -  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -*-  -  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -2-*-2-0-  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -*-2-  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -  -  -  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -  -  -  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
-  -  -  -  -  -  -  -  -  -  -  -  -  -
  |  |  |  |  |  |  |  |  |  |  |  |  | 
Простейший варриант
2-препятствие, которое  надо обойти
0 -точка начала
*-путь обхода




Это сообщение отредактировал(а) ano360 - 14.1.2007, 13:10

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

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

Интересно, но можно чуть чётче, если кординаты теже, то как хоть примерно искать путь?

Добавлено @ 13:51 

Всё дело в том , яято припятствий очень много, а не одно

Такая идея появилась.

1. искать путь методом волны от начальной точки.
2. где две волны, обогнув препятствие встретиться,
3. найти коратчайший путь, занося всё его кординаты пути в массив, 
4. Проверить, окружают ли кординаты в массиве враж. точку(данный алгоритм давно мной написан и гениально прост)
5. Если, да, сохранить эти кординаты в другом массиве minWay. и сохранить длинну длинну пути в новой переменной
    если нет,ничего не сохранять.
6. выбрать другую точку, где волны встречаются, перейти к пункту 3, после проверить длинну нового пути и кратчайшего и так, пока не израсходуем все точки пересечения двух волн.

minWay-здесь кординаты минимального пути.

работоспособно?
Замечания?



Это сообщение отредактировал(а) ano360 - 14.1.2007, 14:07

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

очень может быть...
кроме непонятности с двумя волнами, вроде, ничего страшного не видно...

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

Какой вы проницательный!!!
Но определять уже окруженные точки я научился, я ии для точек пишу. 
мне надо знать кратчайший путь от точки до неё при этом окружив вражеские, пееход как по своим, так и по пустым клеткам.
И после, на этом пути, исходя уже из други алгоритмов, ИИ будет выбирать и ставить точку.

А волновой алгоритм не устроит?
Берем случайную точку на расстоянии от нашей в разность хода(ну придумай че-нить). Затем другую. Посредством нескольких переходов вернемся обратно... Только другим путем

Вот это мысль! Только волна действительно одна  Но придумать же можно описание события: "точку проверяют с двух сторон".

довольно размыто и неопределённо, можете немного чётче 



Есть хорошая идея!!!!!!!!!!
Перед тем как до неё дойти очень много алгаритмов пришлось отбросить

знаю как проследить разбивку волны на две.
В основе-простой волновой олгаритм

n -порядковый номер волны. Первый раз 0, потом 1, потом 2 и т.д.


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

Добавлено @ 18:19 
нет.......
если волна разбивается в одном месте!,run_n обойдёт с другой стороны


    3333333
    3222223
    3211123
    3210123
    3211123
    3222223
    333*333
          4 

Это сообщение отредактировал(а) ano360 - 15.1.2007, 18:26