Тера Инкогнита, Вершина задается двумя координатами. Их, правда, удобнее перенумеровать. Напишите 2 функции, одна по координатам выдаст номера вершин (можно взять формулу x*n+y, например).
Вторая функция должна по вершине возвращать ее координаты. Можно или реализовать обратную формулу (i/n, i%n).
Но это работает только в квадратной сетке. Для треугольной сетки вам может быть удобнее сложить координаты вершин в список и эти 2 функции будут соответственно, искать координаты в списке или возвращать i-ый элемент списка.
Вот теперь граф. Граф - это фактически список списков. Для каждой вершины вам надо хранить ее соседей. Надо для каждой вершины заданной координатами (x,y) добавить в ее список соседей вершины (x-1, y), (x+1,y) (x, y-1) и (x,y+1), если они есть, естественно. Для вершины (0,0) - в углу - есть только 2 соседа. Надо не добавлять вершины с отрицательными координатами или координатами >=n.
Создали вы граф. Запустите на нем дейкстру, а лучше обход в ширину. Этот алгоритм вернет вам список вершин в пути. По номерам вершин вы можете восстановить координаты. Вот у вас уже есть весь путь.
Тера Инкогнита, Это не игры. Это тривиальные заскриптованные анимации вообще без логики. На том же юнити это делается за тот же час а то и быстрее. Ваш скретч лучше всяких C# и Java только тем, что там встроенная систма для рисования спрайтов, воспроизведения звуков и обработки кликов. Фактически - это игровой движок как юнити. Его и надо сравнивать с игровыми движками. Только вместо нормального кода и удобных инструментов там кастрированная система визуального перетаскивания блоков. Это может казаться удобнее новичку, который ни разу в жизни ни писал код. Но это медленнее, чем печатать код, и это неподдерживаемо - читать эти блоки сложнее и редактировать - сущий ад.
Кроме того сам движок весьма кастрирован. Там есть 3d графика? Работа с ресурсами? Насколько интерпретация этих блоков быстра? Там есть JIT-компиляция? Про структуры данных я уже спрашивал...
Короче, это неплохой инструмент для обучения маленьких детей, как и логомиры. Но для бизнеса он не подходит.
Тера Инкогнита, Тут не надо знания математики. Надо лишь немного абстрактного мышления. И его придется потренировать как-то. Потому что без этого игры писать не получится. Вернее, вот такие тривиальные анимации, как в ваших примерах, вы еще сможете сделать, а вот треугольную сетку - уже никак.
Попробуйте сначала сделать тупо квадратную сетку. Это чуть проще. Раз дейкстру у вас учат в 7-ом классе, то вы должны ее понимать. Вам осталось только скормить ей какой-то граф. Для квадратной сетки граф построить просто - вершина заданна двумя координатами. Ребра есть на соседние (там одна из координат изменена на +1 или -1).
Тера Инкогнита, А хеш-таблицы, множества на бинарных деревьях, вот-это-вот все там есть? Впрочем, это не важно. Вам понадобятся максимум списки-списков.
Если используем массив, то при вставке нового элемента есть еще накладные расходы на увеличение длинны массива и это может быть по затрата больше чем все остальное.
Но массив можно изначально завести на максимальное количество элементов. Или использовать какой-нибудь нормальный массив, вроде std::vector в C++, который за счет немного большего потребления памяти позволяет добавлять новые элементы за константное время, даже с учетом переаллокации.
Тера Инкогнита, В этом скретче вообще переменные есть? Или все сущности - это спрайты какие-то? Тогда это не язык программирования. Это редактор анимаций в сильно извращенном формате.
MARK KURDA, Можно и уменьшать и увеличивать количество, если вы с конца удаляете/добавляете. Для этого и есть 2 указателя на начало и на конец массива. При добавлении платформы в конец надо сдвинуть конечный указатель. Пока всего в циклическом массиве элементов не больше, чем размер выделенного массива - все работает.
Вот если вы новую платформу в середину добавляете или удаляете, то тут уже надо смотреть на то, как часто у вас какие операции происходят. Может быстрее будет как в моем ответе вставкой делать. Или будет лучше вместо массива вообще использовать бинарное балансированное дерево (какой-нибудь std::set в C++). В этой структуре можно добавлять, удалять что угодно и искать ближайшую к игроку платформу за логарифм и итерироваться по всем платформам почти также быстро, как в массиве. Вам даже ничего своего писать, скорее всего не придется - просто использовать стандартную структуру языка.
MARK KURDA, Я так понял, у вас каждый раз нижняя платформа перемещается в самый верх? Тогда их даже сортировать не надо. Используйте циклический массив. Сами платформы вообще не перемещаются в массиве - у вас будет 2 индекса: начало массива и конец. Они могут быть в массиве как угодно: например, начало - индекс 5, конец - индекс 4. И получается, что платформы в массиве по порядку идут так: {5, 6, 7, ..., n-1, 0, 1, 2, 3, 4}
В таком массиве можно точно также устраивать бинарный поиск. Просто забудьте что ваш массив циклический. Когда вам нужно обратиться к i-тому по порядку элементу вы обращаетесь к (be+i)% n индексу в массиве.
Потом, вам не нужен бинарный поиск, если игрок не может телепортироватся. Можно поддерживать индекс платформы, на которой игрок находится. И менять его при движении персонажа.
EvgenyApMr, Нет, случайно набрасывать слова в код - это не программирование. Сначала опишите алгоритм словами. Порисуйте примеры на бумажке, убедитесь, что оно работает, и потом программируйте.
Karpion, Я описал стек, реализованный в виде списка внутри используемого массива. Чем очередь лучше стека? В принципе, все то же самое, но надо два указателя вместо одного: на начало и конец очереди. И в предложенном мной решении никакой памяти выделять не надо.
Но это все только если забить на требование выбора самой левой ячейки.
1HAWK1, Первые несколько секунд посмотрел - там говорят, почему нельзя делить на ноль. Это видео противоречит вашему утверждению в вопросе. Не та ссылка? Или там какое-то тайное знание? Или это вы просмотры пытаетесь набить таким методом?
Лев Александров, Ах да, тут добавляется новый элемент не в самую левую ячейку, а в последнюю освобожденную. Но зато добавление и удаление за константу и дополнительной памяти - одна переменная.
Если вам обязательно нужно в самую левую ячейку класть, то придется реализовывать, например, дерево отрезков, или бинарную кучу. Это делается только на массивах и циклах. В этих структурах данных можно будет искать самую левую ячейку, добавлять ячейки и удалять самую левую за логарифм.
Если скорость не важна, то пишите тупой перебор - циклом пройдитесь по массиву, пока пустую ячейку не встретите.
Коммкнтарий про вектор: постоянно делать push_back не особо медленнее, чем сначала выделить память и просто заполнять массив.
Медленнее, конечно, но не ОООЧЕНЬ дорого.
Это потому что вектор каждый раз, когда в нем нет места, удваивает массив. В итоге общее количество копирований элементов будет линейно и общий объем выделенной памяти - тоже. Чем больше вы элементов складываете, тем меньше разница.
Если вы знаете, сколько элементов будет - то reserve стоит сделать. Но не стоит избегать push_back, как огня из-за его медленности.
Вторая функция должна по вершине возвращать ее координаты. Можно или реализовать обратную формулу (i/n, i%n).
Но это работает только в квадратной сетке. Для треугольной сетки вам может быть удобнее сложить координаты вершин в список и эти 2 функции будут соответственно, искать координаты в списке или возвращать i-ый элемент списка.
Вот теперь граф. Граф - это фактически список списков. Для каждой вершины вам надо хранить ее соседей. Надо для каждой вершины заданной координатами (x,y) добавить в ее список соседей вершины (x-1, y), (x+1,y) (x, y-1) и (x,y+1), если они есть, естественно. Для вершины (0,0) - в углу - есть только 2 соседа. Надо не добавлять вершины с отрицательными координатами или координатами >=n.
Создали вы граф. Запустите на нем дейкстру, а лучше обход в ширину. Этот алгоритм вернет вам список вершин в пути. По номерам вершин вы можете восстановить координаты. Вот у вас уже есть весь путь.