Russian Qt Forum

Добрый день

Увидел задачку, и очень она мне понравилась
Правда совсем нет мыслей как делать :) А у Вас?

Спасибо

Нет данных о видимости.

На сколько клеток есть данные? Или всё поле сразу дано? Или же транспортер слепой и знает только  можно в том направлении ехать или нельзя?/* Что будет при столкновение с камнем? мало данных.*/

update: увидел про камень.

Если нет видимости, то простой алгоритм обхода. Если есть - более сложные алгоритмы.

Мне кажется алгоритм Прима здесь применим.

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

Если будут усложнения получится маленький ботик для этой игры (задачи).
 

PS Я в принципе ничего другого от Igors не жду :) Отсутствие конкретизированных требований и ограничений и неясная задача :-D Стандарт.

Можно сделать арену и гонять там ботов, боты делать на javascript. Нужно только определится с API.

• Если "видимость" - с алгоритмом проблем нет. Задача решается обходом дерева перемещений-возвратов, с оценкой весов путей.
• Если видимости нет - сложнее. Можно попробовать обучающиеся нейронные сети, но это сработает только в том случае, если разброс "сущностей" на поле - случайный-неравномерный или закономерный

ИМХО конечно.

В принципе несложная задачка, решаемая простыми алгоритмами. НО... Но Igors мастер таких вот размытых задач :P

"Ну Вы блин даете" :) Зачем говорить о некой "видимости" если условие начинается со слов "дано поле"? Наверное пока дочитали до конца - уже забыли начало :) И прекрасный вопрос "должен ли транспортер выжить?" - а сами-то как думаете? Или "начальное поле" - типа нет, сначала он на вертолете летает, а потом уж....   :)  

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

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

Хотя я в упор не вижу что это меняет - с этими условиями или др - все равно ни одной мысли нет  :)

Как только я слышу что-то типа "проблем нет" - мгновенно в голове проносится фразв "це дiлa не буде". Максимум человек отпихнется ссылкой на нечто (часто вообще не имеющее отношения) - и все. Или я ошибаюсь ?  :)  

Ну пошли понты  :)

Но могут взять за жопу и предложить ответить за свою похвальбу  :)

Видимость я спрашивал.

Дано поле 40 на 40.

Оно закрыто как в сапёре, ИЛИ  мы имеем данные о том, что находится в каждой клетке данного поля?

PS ваша (или скопированная) формулировка имеет двоякое значение. То ли мы имеем все данные, то ли мы имеем только размеры поля.

PPS про выживание вопрос интересный, а не глупый. Открытие последней клетки с капканом (-10hp) убьёт транспортёр (10hp) и что будет? победа или поражение? :D В простых играх этот момент меня иногда выбешивал :D Когда всё, босса завалил, счастливый стоишь и оп - яд тебя добивает :D И вместо "Вы прошли игру" -> "Ты сдох мерзкий герой" :D

Отвечаю - весь расклад известен, все клетки "открыты"

Ok

Не согласен. Перемещение требует -1 энергии.

Ok

Тоже не согласен. По мне, так и первое и второе должно исчезнуть после контакта.

А здесь интересно экспериментировать. Описал логику, запустил в арене, посмотрел результат. Поменял карту, запустил, посмотрел.
Для начала лобовая логика: двигаться по линии вправо, пока не дойдешь до конца карты -> опуститься вниз на одну клетку и двигаться влево, до начала карты. А потом можно пробовать варианты с обходом препятствий.
Или второй вариант, двигаться по спирали от стартовой точки.
Много всего можно придумать, но интересно будет когда будет арена и визуально можно будет смотреть на действия бота.

Здесь тоже не соглашусь. По мне интересней, если бот будет иметь ограниченную видимость.

Учитывая последующие "уточнения" - я бы предложил алгоритм, похожий на "обойти ходом шахматного коня поле". Идея "правильности" алгоритма - планировать так последующий ход, чтобы как можно плотнее прижиматься к краям поля. Иными словами - сужающаяся спираль. Я бы пробовал именно так.

Да пожалуйста, можно принять любой из вариантов, но, во всяком случае на данном этапе я не вижу никакой разницы

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

Если капканы и еда не исчезает, пойдёт алгоритм проезда по всем капканам до 10 hp и поездка нажраться )

Стоп, капканы бот видеть тоже не должен, иначе теряется их смысл. :)

IMHO, здесь не идет речь четко обойти все (без исключения) клетки, требуется обойти как можно больше. Т.е. это соревнования стратегий.
А для этого нужно проводить "бои" и сравнивать.

Вы все-таки уходите/углубляйтесь "в решение", а не в "условие"  :)

Тут такая засада. Пока нет начальных данных, решение может плавать :D

Вот если бот видит все капканы, но незнает сколько они дают - будет в разы легче :D

Вы мне предлагаете написать арену?
Идеи следующий:
боты пишутся на javascript, ядро предоставляет боту небольшое api для исследования карты: посмотреть что в соседних ячейках и переместиться в соседнюю ячейку. Если в клетке:
* пусто - -1 энергии и переместиться на клетку;
* камень - -1 энергии и остались на месте;
* капкан - -10 энергии и переместиться на клетку;
* еда - +10 энергии и переместиться на клетку.

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

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

еще не сказано можно ли посещать клетки больше одного раза.

Согласен, в постановке автора - все поле открыто (и все веса известны). Хотя и закрытое (полуоткрытое) поле - тоже интересно. Повторюсь - пока не видно что вообще делать  :)

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

Ну "не запрещаю" :) Мне лично неясно что писать - нет идей. Подумаю, если что-то будет - завтра напишу (чтобы по пустому не месить)

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

А если так?

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

на словах просто, я вот например слабо себе представляю реализацию графа :)

Ну вроде граф можно представить в виде матрицы смежности. Либо, через структуры. Я как раз читаю книгу "Фунд. алгоритмы на графах с++", там вроде все на матрицах смежностей. У Шилдта в справочнике, вроде как задачи с графами были на структурах.

p.s.: мне даже кажется, что сложность не в представлении графа, а в решении задачи связности узлов: знать какие узлы мы уже посетили, как дойти до другого узла из текущего и т.д. Короче я пока застрял на первой главе и дальше не идёт!:)

Заметно. Ну да ладно, я беру отгул из этой темы - на работе запара, вы тут порешайте, арену сделайте, графики постройте пока без меня :D

Что совсем никаких?

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

Ниже я это покритикую, но приятно видеть что человек думает (а не только мордой в салат/букварь  :))

Очевидно что "локальный" выбор ребра/хода как минимум не имеет ничего общего с оптимальностью. Ну ладно, шли-шли и в конце-концов уперлись в край. Переходим в ближайшую. Оттуда еще в ближайшую и.т.д. Так? (если нет поправьте). Если переход в ближайшую неосуществим (нет ребра), то возвращаемся на шаг назад  и оттуда смотрим ближайшую (а как иначе?). Это выглядит как-то "хаотично" (типа наркоман ищет дозу), ну оптимальностью здесь точно не пахнет. Однако для "просто обхода" по-видимому годится (ведь и этого не было).

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

Это др задача - типа "движок", у бота какой-то алгоритм, дальше жизнь покажет. Все-таки изначально это задача оптимизации, Вы ее "узурпировали". Да, Ваше предложение интересно, но тогда давайте подходить профессионально - кому мы это впарим? А то, знаете, энтузиазм быстро затухает (см напр последний пост Вереса), да и вообще я меркантильный человек  :) 

Не надо на меня валить. У меня рефлектометр на запросы еле отвечает, мне с ним разбираться надо. *!battle cry!*

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

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

Для этого нужны идеи и знания. Чем вы готовы помочь проекту?
Идея с ареной и ботами на js у меня уже давно сидит в голове. Правда изначально, это должны были быть торговые боты. :)

Жизнь научила - только так.

Хммм... это типичное обманчивое впечатление "резвого старта"

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

Да, так и есть. Алгоритм Прима, если граф представлен в виде матрицы по вики имеет сложность О(V^2)

Странно, вообще жизнь должна была научить "Сначала идеи, потом деньги", но вам, наверное, везет с заказчиками.

Вам нужно учиться оценивать объем и сложность проекта не основываясь на впечатлениях. Будете меньше подводить заказчика.

Пишите проще, я не знаю js поэтому не могу возиться с алгоритмами используя его. Хотя для ботов он очень хорош, как и другие скриптовые языки.

Ну вас о помощи и не просили.
А бесплатный проект легко превращается в платный, но это если подумать: меняем "рычаги" + визуализатор и ядро уже может запускать торговых ботов или контролировать 100500 разных датчиков и вентелей. Это по сути среда, где могут параллельно выполняться куча маленьких независимых процессов на простом скриптовом языке.

Не засоряйте эфир :)

Возможно Вы увлечены красивой идеей/задумкой, но ей явно недостает "реализьма", а Вам - того что называется "хваткой". Пройдет напр год, и мечта останется мечтой, как, вероятно, уже было не один год. Или я ошибаюсь?  :)

Вот я и предлагаю его сделать, тем более работы там не так много. Если найдутся желающие, то сделаем.



Я понимаю, что вы ничем не сможете нам помочь, в связи с полным отсутствием знание в этой области. Поэтому я откланиваюсь. :)

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

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

Ну конечно задана, изначально танк (транспортер) там стоит

Понимаю, но давайте исходить из разумного правила: "заказчик не оговорил - имею право принять/решить по своему усмотрению". Кстати перебором (тупенький "алгоритм с развратом") я тоже примерно вижу. Сравнимся? Вы первый или я (как хотите)

я вот думал, что можно начинать движение с любой точки с краю