Ваш вопрос охватывает слишком много вопросов для подробного ответа. Я разделил его на две темы: игровое поле и представление и Четырехъядерные деревья , которые кратко охватят два ваших вопроса.
Я добавил пример, который реализует оба предмета на самом базовом c уровне. Используйте пример, чтобы изучить более тонкие детали. Если у вас есть вопросы, задавайте их в комментариях или в качестве новых вопросов SO.
Игровое поле и вид
Игровое поле - это вся карта. (см. пример playfield). Он не содержит пикселей, он содержит только элементы для отображения и взаимодействия. (см. пример playfield.quadMap playfield.visibleItems и mapItems)
Представление - это холст.
Он не больше дисплея и содержит только пиксели.
Вид не зависит от игрового поля и может быть расположен, повернут и масштабирован. Пример только позиционирует вид.
Вид установлен относительно чего-то интересного в игровом поле. Например плеер. (см. пример playfield.setView)
Вы устанавливаете вид (top left), занимая положение игроков и вычитая половину ширины и высоты видов.
Чтобы убедиться, что вид не выходит за пределы игрового поля go, убедитесь, что верхний левый угол не меньше 0, а верхний левый плюс ширина и высота вида не больше ширины и высоты игрового поля. (см. пример playfield.setView)
Чтобы использовать вид, установите преобразование холста таким образом, чтобы его начало составляло -top и -left, а затем нарисуйте элементы в этом нормальном положении.
Quad деревья
Когда у вас большое игровое поле со множеством предметов, устройство может потребовать много усилий для отрисовки всех предметов. Даже предметы, находящиеся вне поля зрения, будут потреблять немного процессорного времени, которое увеличивается и делает игру очень медленной.
Для повышения производительности вам нужно только рисовать (и обновлять) видимые элементы. Однако процесс поиска видимых элементов может добавить столько же нагрузки, сколько просто вызов функций рисования. Вам необходимо использовать метод, который позволяет быстро находить видимые элементы без необходимости тестировать каждый элемент в игровом поле.
В 2D это можно сделать с помощью специального типа связанного списка, называемого четырехугольным деревом.
- Четырехугольное дерево состоит из квадратов. У каждого квадрата есть топор, позиция y, ширина и высота. Например,
Quad - Первый квад имеет тот же размер, что и игровое поле. В примере это квадрат 16000 пикселей.
- Каждый квад также может иметь 4 субквада, представляющих квад, разделенный на 4. См. Пример
Quad.prototype.divide - Вы повторяете для каждого субквада, дайте каждому 4 больше суб квадров. Вы устанавливаете максимальную глубину, то есть количество раз, когда вы делите субквадр на большее количество субквадов. (в данном примере
maxDepth равно 5) - Таким образом, наименьший квад в примере - это игровое поле
size / (2 ** maxDepth) === 16000 / 32 === 500, означающее, что оно охватывает 500 на 500 пикселей игрового поля. - Внизу из дерева квадов вы храните элементы, которые перекрывают этот квад. Элемент может перекрывать несколько квадов, каждый квад должен перекрывать этот элемент. (в данном случае элемент представляет собой просто прямоугольник с
x, y, w, h и col или) - Вы можете проверить, перекрывает ли какой-либо четырехугольник текущий вид. См. Пример (
Quad.prototype.isInView). Если этого не происходит, он и все его подваги и элементы, которые они содержат, не видны. Это очень быстро устраняет необходимость проверять до 3/4 элементов.
Объект игрового поля содержит самый верхний элемент Quad. Когда вы устанавливаете представление playfield.setView, оно создает преобразование вида и создает карту всех элементов во всех видимых квадратах. Когда setView возвращает карту, playfield.visibleItem содержит все элементы в четырехугольниках, которые перекрывают вид.
Поскольку элементы карты могут быть в нескольких четырехугольниках одновременно, вам необходимо быстро создать список элементов без повторяя тот же пункт. Вы можете сделать это с помощью Map или Set (они встроены в JavaScript объекты) и позволяют избежать необходимости проверять, есть ли элемент в списке.
Пример
Используйте клавиши СТРЕЛКА для перемещения. Вы должны щелкнуть холст , чтобы начать, так как фрагменты SO не будут автоматически фокусировать клавиатуру.
Карта playfield очень велика 16 000 на 16 000 пикселей, и на карте 10 000 элементов.
Использование четырехугольного дерева для поиска видимых элементов позволяет анимировать вид в режиме реального времени со скоростью 60FPS.
const keys = { // keys to listen to
ArrowUp: false,
ArrowLeft: false,
ArrowRight: false,
ArrowDown: false,
};
document.addEventListener('keydown', keyEvent);
document.addEventListener('keyup', keyEvent);
document.addEventListener("click",()=>requestAnimationFrame(mainLoop),{once:true});
var startTime;
var globalTime;
const mapItemCount = 10000;
const maxItemSize = 120; // in pixels
const minItemSize = 20; // in pixels
const maxQuadDepth = 5;
const playfieldSize = 16000; // in pixels
var id = 1; // unique ids for map items
const mapItems = new Map(); // unique map items
const directions = {
NONE: {idx: 0, vec: {x: 0, y: 0}},
UP: {idx: 3, vec: {x: 0, y: -1}},
RIGHT: {idx: 0, vec: {x: 1, y: 0}},
DOWN: {idx: 1, vec: {x: 0, y: 1}},
LEFT: {idx: 2, vec: {x: -1, y: 0}},
};
const ctx = canvas.getContext("2d");
function mainLoop(time) {
if(!startTime) { startTime = time }
globalTime = time - startTime;
playfield.sizeCanvas();
ctx.setTransform(1,0,0,1,0,0);
ctx.clearRect(0,0,canvas.width,canvas.height);
player.update();
playfield.setView(player); // current transform set to view
playfield.drawVisible();
player.draw();
info.textContent = `Player: X:${player.x|0} Y${player.y|0}: , View Left:${playfield.left | 0} Top:${playfield.top | 0} , visibleItems: ${playfield.visibleItems.size} of ${mapItems.size}`;
requestAnimationFrame(mainLoop);
}
function Quad(x, y, w, h, depth = maxQuadDepth) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
if (depth > 0) { this.divide(depth) }
else { this.items = [] }
}
Quad.prototype = {
divide(depth) {
this.subQuads = [];
this.subQuads.push(new Quad(this.x, this.y, this.w / 2, this.h / 2, depth - 1));
this.subQuads.push(new Quad(this.x + this.w / 2, this.y, this.w / 2, this.h / 2, depth - 1));
this.subQuads.push(new Quad(this.x + this.w / 2, this.y + this.h / 2, this.w / 2, this.h / 2, depth - 1));
this.subQuads.push(new Quad(this.x, this.y + this.h / 2, this.w / 2, this.h / 2, depth - 1));
},
isInView(pf) { // pf is playfield
return !(this.x > pf.left + pf.cWidth || this.x + this.w < pf.left || this.y > pf.top + pf.cHeight || this.y + this.h < pf.top);
},
addItem(item) {
if (!(item.x > this.x + this.w || item.x + item.w < this.x || item.y > this.y + this.h || item.y + item.h < this.y)) {
if (this.subQuads) {
for (const quad of this.subQuads) { quad.addItem(item) }
} else { this.items.push(item.id) }
}
},
getVisibleItems(pf, itemMap, items = new Map()) {
if (this.subQuads) {
for (const quad of this.subQuads) {
if (quad.isInView(pf)) { quad.getVisibleItems(pf, itemMap, items) }
}
} else {
for (const id of this.items) { items.set(id, itemMap.get(id)) }
}
return items
}
}
// only one instance then define as object
const playfield = {
width: playfieldSize,
height: playfieldSize,
view: [1,0,0,1,0,0], // view as transformation matrix
cWidth: 0, // canvas size
cHeight: 0, // canvas size
top: 0,
left: 0,
sizeCanvas() {
if(canvas.width !== innerWidth || canvas.height !== innerHeight) {
this.cWidth = canvas.width = innerWidth;
this.cHeight = canvas.height = innerHeight;
}
},
setView(player) {
var left = player.x - this.cWidth / 2;
var top = player.y - this.cHeight / 2;
left = left < 0 ? 0 : left > this.width - this.cWidth ? this.width - this.cWidth : left;
top = top < 0 ? 0 : top > this.height - this.cHeight ? this.height - this.cHeight : top;
this.view[4] = -(this.left = left);
this.view[5] = -(this.top = top);
ctx.setTransform(...this.view);
this.visibleItems.clear();
this.quadMap.getVisibleItems(this, mapItems, this.visibleItems);
},
drawVisible() {
for(const item of this.visibleItems.values()) { item.draw() }
},
quadMap: new Quad(0, 0, playfieldSize, playfieldSize),
visibleItems: new Map(),
}
function MapItem(x, y, w, h, col = "#ABC") {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
this.col = "#ABC";
this.id = id++;
mapItems.set(this.id,this);
playfield.quadMap.addItem(this);
}
MapItem.prototype = {
draw() {
ctx.fillStyle = this.col;
ctx.fillRect(this.x, this.y, this.w, this.h);
}
}
addMapItems(mapItemCount)
function addMapItems(count) {
while (count-- > 0) {
const x = Math.random() * playfield.width;
const y = Math.random() * playfield.height;
const w = Math.random() * (maxItemSize - minItemSize) + minItemSize;
const h = Math.random() * (maxItemSize - minItemSize) + minItemSize;
const item = new MapItem(x,y,w,h);
}
}
// only one instance then define as object
const player = {
x: 1200,
y: 1200,
speed: 10,
image: undefined,
direction: undefined,
draw() {
ctx.fillStyle = "#F00";
ctx.save(); // need to save and restore as I use rotate to change the current transform that
// holds the current playfield view.
const x = this.x;
const y = this.y;
ctx.transform(1,0,0,1,x,y);
ctx.rotate(this.direction.idx / 2 * Math.PI);
ctx.beginPath();
ctx.lineTo(20, 0);
ctx.lineTo(-10, 14);
ctx.lineTo(-10, -14);
ctx.fill();
ctx.restore();
},
update() {
var dir = directions.NONE;
if (keys.ArrowUp) { dir = directions.UP }
if (keys.ArrowDown) { dir = directions.DOWN }
if (keys.ArrowLeft) { dir = directions.LEFT }
if (keys.ArrowRight) { dir = directions.RIGHT }
this.x += dir.vec.x * this.speed;
this.y += dir.vec.y * this.speed;
this.x = this.x < 0 ? 0 : this.x > playfield.width ? playfield.width : this.x;
this.y = this.y < 0 ? 0 : this.y > playfield.height ? playfield.height : this.y;
this.direction = dir;
}
};
function keyEvent(e) {
if (keys[e.code] !== undefined) {
keys[e.code] = e.type === "keydown";
e.preventDefault();
}
}
canvas {
position: absolute;
left: 0px;
top: 0px;
}
#info {
font-family: arial;
position: absolute;
left: 0px;
top: 0px;
font-size: small;
}
<canvas id="canvas"></canvas>
<div id="info">Click to start</div>