Обход препятствий (модель движения толпы к выходу)

[mrandrew1990]

Всем доброго времени суток. Уважаемы товарищи-программисты, столкнулся с проблемой при написании программы (модель движения толпы). Суть такова – поле, на котором все происходит, представляет собой сетку из клеток; одна единственная клетка – выход, другие либо пустые (белый цвет), либо там люди (зеленый цвет) или погибшие люди в результате паники (красный цвет), либо черный (препятствие). Так вот не могу довести до ума алгоритм движения людей к выходу при столкновении с препятствиями…. По идее надо, допустим, если перед человеком сверху (или снизу от него) в горизонтальную (либо вертикальную слева или справа от него) линию (т.е. несколько подряд клеток черного цвета в один ряд) – нужно чтобы он обходил эту стенку как полагается относительно выхода (т.е. также стремился достигнуть выхода), т.е. не долбился в нее (как у мя сейчас происходит, при этом он стопорится там и умирает как бы), а должно быть чтобы он вдоль стенки двигался пока не найдет свободную клетку для движения к выходу, т.е. вперед…. С боковыми, т.е. вертикальными препятствиями тоже так…. Вот не пойму как это дело соорудить… Вот схема, которую нарисовал как должно быть

[vovken1997]

Алгоритм нахождения кратчайшего пути "A*" вам в помощь. Расчитайте его для каждого человека.

[evg_m]

при выборе направления проверяй доступность пути(есть препятствие типа стена) и при его наличии корректруй направление.

[s-andriano]

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

Алгоритм нахождения кратчайшего пути "A*" вам в помощь. Расчитайте его для каждого человека.

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

[mrandrew1990]

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

[s-andriano]

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

т.е. я координаты не могу знать.

Это как?

и получается придется еще проверять условие кроме наличия препятствия - нет ли там человека....

Причем есть два варианта:
1. Считать другого человека за препятствие как при поиске пути, так и при передвижении.
2. Считать за препятствие только для передвижения, путь строить без учета других людей.

[mrandrew1990]

Сообщение от s-andriano

Это как? Причем есть два варианта:
1. Считать другого человека за препятствие как при поиске пути, так и при передвижении.
2. Считать за препятствие только для передвижения, путь строить без учета других людей.

ну в принципе объединить и людей и препятствие - тупо проверять, занята ли клетка (пуста или нет).... наверное так...

[s-andriano]

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

ну в принципе объединить и людей и препятствие - тупо проверять, занята ли клетка (пуста или нет).... наверное так...

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

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