ÁLGEBRA ARCADE

Fase 5.4: O GPS do Universo

Manual da Fase: Bases e Coordenadas

Todo universo de jogo precisa de um sistema de coordenadas, um "GPS" para localizar objetos. Em Álgebra Linear, esse GPS é chamado de Base. Uma base é um conjunto de vetores "perfeito": pequeno o suficiente para não ter redundâncias (Linearmente Independente) e poderoso o suficiente para alcançar qualquer ponto do universo (Gera o Espaço).

Uma vez que temos uma base, a localização de qualquer vetor pode ser descrita por um conjunto único de coordenadas, que nos dizem "quanto" de cada vetor da base precisamos para chegar lá. A mesma localização pode ter coordenadas diferentes dependendo do GPS (base) que você está usando!

Missão Principal: Encontrar Coordenadas

Para encontrar as coordenadas \(\vec{c}\) de um vetor \(\vec{v}\) na base \(B=\{\vec{b_1}, \dots, \vec{b_n}\}\), resolva o sistema linear:

\[ B\vec{c} = \vec{v} \quad \text{ou} \quad c_1\vec{b_1} + \dots + c_n\vec{b_n} = \vec{v} \]

O Baú do Tesouro Inalcançável (Span)

Objetivo da Missão: Verificar se um vetor pertence ao espaço gerado (span) por outros dois.

Um baú de tesouro está na localização \(\vec{w}=(7, -1, 5)\). Seu personagem tem duas habilidades de movimento: "Salto" \(\vec{u}=(1, 2, -1)\) e "Dash" \(\vec{v}=(3, 1, 2)\). É possível chegar ao baú combinando múltiplos desses movimentos a partir da origem? Em outras palavras, \(\vec{w}\) está no \(\text{span}\{\vec{u}, \vec{v}\}\)?

Pedir Dica ao Mestre do Jogo...

Você precisa encontrar escalares \(c_1, c_2\) tais que \(c_1\vec{u} + c_2\vec{v} = \vec{w}\). Isso se traduz em um sistema de 3 equações e 2 incógnitas. Se o sistema tiver solução, é possível.

Ver Detonado...
  1. Monte a equação vetorial \(c_1\begin{pmatrix}1\\2\\-1\end{pmatrix} + c_2\begin{pmatrix}3\\1\\2\end{pmatrix} = \begin{pmatrix}7\\-1\\5\end{pmatrix}\).
  2. Converta em um sistema linear: \(c_1+3c_2=7\), \(2c_1+c_2=-1\), \(-c_1+2c_2=5\).
  3. Resolva o sistema. Das duas primeiras equações, você pode encontrar valores para \(c_1\) e \(c_2\).
  4. Verifique se esses valores satisfazem a terceira equação. Se sim, o sistema é consistente e o vetor pertence ao span.
Teste de consistência: \(A\vec{c}=\vec{w}\)

Conexão com o Mundo dos Jogos: O `span` de um conjunto de movimentos define todas as áreas "alcançáveis" do jogo. Se um objetivo está fora do `span`, o jogador precisa adquirir uma nova habilidade para chegar lá. É um conceito fundamental para o design de progressão em jogos.

O GPS Perfeito (Verificação de Base em R²)

Objetivo da Missão: Usar o determinante para verificar rapidamente se dois vetores formam uma base para \(\mathbb{R}^2\).

Um engenheiro propõe um novo sistema de navegação para o mapa 2D usando os vetores \(\vec{b_1}=(3,1)\) e \(\vec{b_2}=(1,2)\). Para que este seja um bom "GPS", os vetores precisam formar uma base. Verifique se eles são Linearmente Independentes e se geram \(\mathbb{R}^2\).

Pedir Dica ao Mestre do Jogo...

Para \(n\) vetores em \(\mathbb{R}^n\), eles formam uma base se, e somente se, a matriz formada por eles tem determinante não-nulo. Este é o atalho mais rápido!

Ver Detonado...
  1. Para verificar se dois vetores em \(\mathbb{R}^2\) formam uma base, basta verificar se são Linearmente Independentes. Se forem, eles automaticamente geram o espaço.
  2. Forme a matriz \(B\) com os vetores como colunas: \(B = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}\).
  3. Calcule o determinante de \(B\). \(\det(B) = (3)(2) - (1)(1)\).
  4. Se o determinante for diferente de zero, os vetores são LI e, portanto, formam uma base para \(\mathbb{R}^2\).
Para \(n\) vetores em \(\mathbb{R}^n\): \(\det(B) \neq 0 \iff\) formam uma base.

Conexão com o Mundo dos Jogos: Uma base é um sistema de coordenadas. A base canônica \(\{\vec{i}, \vec{j}\}\) é o sistema "Norte/Leste". Uma base diferente pode ser um sistema "Nordeste/Noroeste", que pode ser mais natural para o movimento em um mapa isométrico, por exemplo.

Coordenadas de Fábrica (Coordenadas na Base Canônica)

Objetivo da Missão: Entender que as coordenadas na base canônica são os próprios componentes do vetor.

A base padrão (canônica) de \(\mathbb{R}^2\) é \(E = \{\vec{e_1}, \vec{e_2}\}\) onde \(\vec{e_1}=(1,0)\) e \(\vec{e_2}=(0,1)\). Se a posição de seu personagem é \(\vec{v}=(7,3)\), quais são suas coordenadas na base canônica? Ou seja, quais \(c_1, c_2\) satisfazem \(c_1\vec{e_1} + c_2\vec{e_2} = \vec{v}\)?

Pedir Dica ao Mestre do Jogo...

Substitua os vetores na equação: \(c_1(1,0) + c_2(0,1) = (7,3)\). O que isso lhe diz sobre \(c_1\) e \(c_2\)?

Ver Detonado...
  1. Escreva a equação vetorial: \(c_1\begin{pmatrix}1\\0\end{pmatrix} + c_2\begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}7\\3\end{pmatrix}\).
  2. Simplifique o lado esquerdo: \(\begin{pmatrix}c_1\\c_2\end{pmatrix} = \begin{pmatrix}7\\3\end{pmatrix}\).
  3. Por igualdade de vetores, concluímos que \(c_1=7\) e \(c_2=3\).
  4. O vetor de coordenadas de \(\vec{v}\) na base canônica, \([\vec{v}]_E\), é \(\begin{pmatrix}7\\3\end{pmatrix}\).
Para a base canônica, \([\vec{v}]_E = \vec{v}\).

Conexão com o Mundo dos Jogos: A base canônica é o sistema de coordenadas padrão de quase todos os motores de jogo. Quando você define a posição de um objeto como `(x, y)`, você está implicitamente usando a base canônica.

Navegando em Outro Idioma (Coordenadas em uma Base Não-Canônica)

Objetivo da Missão: Calcular as coordenadas de um vetor em uma base diferente da padrão.

Você entra em uma "zona distorcida" cujo sistema de eixos é definido pela base \(B = \{\vec{b_1}, \vec{b_2}\}\), onde \(\vec{b_1}=(1,1)\) e \(\vec{b_2}=(0,2)\). Sua posição no mapa global ainda é \(\vec{v}=(3,5)\). Quais são suas coordenadas nesta nova zona distorcida? Encontre \([\vec{v}]_B\).

Pedir Dica ao Mestre do Jogo...

Você precisa resolver a equação \(c_1\vec{b_1} + c_2\vec{b_2} = \vec{v}\). Monte o sistema linear e encontre \(c_1\) e \(c_2\).

Ver Detonado...
  1. Monte a equação vetorial: \(c_1\begin{pmatrix}1\\1\end{pmatrix} + c_2\begin{pmatrix}0\\2\end{pmatrix} = \begin{pmatrix}3\\5\end{pmatrix}\).
  2. Converta em um sistema linear: \(c_1 = 3\) e \(c_1 + 2c_2 = 5\).
  3. Resolva o sistema. A primeira equação já nos dá \(c_1=3\). Substituindo na segunda, temos \(3 + 2c_2 = 5\), o que leva a \(c_2=1\).
  4. O vetor de coordenadas é \([\vec{v}]_B = \begin{pmatrix}3\\1\end{pmatrix}\).
Resolver \(B\vec{c}=\vec{v}\) para encontrar \(\vec{c} = [\vec{v}]_B\).

Conexão com o Mundo dos Jogos: Isso acontece constantemente em jogos 3D. A câmera tem seu próprio sistema de coordenadas (base). Para renderizar a cena, o motor precisa calcular as coordenadas de todos os objetos do mundo em relação à base da câmera.

Decodificando o Sinal (Encontrar Vetor a partir de Coordenadas)

Objetivo da Missão: Dado um vetor de coordenadas e uma base, calcular o vetor original no espaço.

Um aliado em uma nave com um sistema de coordenadas local diferente, definido pela base \(B = \{\vec{b_1}, \vec{b_2}\}\) onde \(\vec{b_1}=(2,-1)\) e \(\vec{b_2}=(1,1)\), envia a localização de um alvo: \([\vec{v}]_B = \begin{pmatrix}3\\-2\end{pmatrix}\). Qual é a localização real do alvo, \(\vec{v}\), no sistema de coordenadas global (canônico)?

Pedir Dica ao Mestre do Jogo...

As coordenadas são os "pesos" da combinação linear. Você já tem os pesos (\(c_1=3, c_2=-2\)) e os vetores da base. Apenas calcule a combinação linear.

Ver Detonado...
  1. Lembre-se da definição de coordenadas: \(\vec{v} = c_1\vec{b_1} + c_2\vec{b_2}\).
  2. Substitua os valores dados na equação: \(\vec{v} = 3\begin{pmatrix}2\\-1\end{pmatrix} + (-2)\begin{pmatrix}1\\1\end{pmatrix}\).
  3. Realize as multiplicações por escalar e a soma dos vetores para encontrar \(\vec{v}\).
\(\vec{v} = B[\vec{v}]_B\)

Conexão com o Mundo dos Jogos: Isso é usado para o movimento de objetos relativos a outros. Por exemplo, a posição de uma torre em cima de um tanque em movimento. As coordenadas da torre são relativas à base do tanque. Para saber a posição global da torre, o motor do jogo realiza exatamente este cálculo a cada quadro.

O Manual de Magias (Verificação de Base para Matrizes)

Objetivo da Missão: Aplicar o conceito de base a um subespaço de matrizes.

O subespaço das matrizes simétricas 2x2, \(S_{22}\), é um "universo" de 3 dimensões. Um antigo manual de magia afirma que as "runas" (matrizes) \( B = \left\{ \begin{pmatrix}1&0\\0&0\end{pmatrix}, \begin{pmatrix}0&1\\1&0\end{pmatrix}, \begin{pmatrix}0&0\\0&1\end{pmatrix} \right\} \) formam uma base para este universo. Verifique se o conjunto \(B\) é Linearmente Independente e se gera \(S_{22}\).

Pedir Dica ao Mestre do Jogo...

Uma matriz simétrica genérica tem a forma \(\begin{pmatrix}a&b\\b&c\end{pmatrix}\). Você consegue escrevê-la como uma combinação linear das matrizes da base? Se sim, elas geram o espaço. Para LI, verifique se a única combinação que resulta na matriz nula é a trivial.

Ver Detonado...
  1. Teste de Geração (Span): Tente escrever uma matriz simétrica genérica como combinação linear: \(c_1\begin{pmatrix}1&0\\0&0\end{pmatrix} + c_2\begin{pmatrix}0&1\\1&0\end{pmatrix} + c_3\begin{pmatrix}0&0\\0&1\end{pmatrix} = \begin{pmatrix}a&b\\b&c\end{pmatrix}\). Isso resulta em \(\begin{pmatrix}c_1&c_2\\c_2&c_3\end{pmatrix} = \begin{pmatrix}a&b\\b&c\end{pmatrix}\), o que mostra que podemos encontrar os coeficientes \(c_1=a, c_2=b, c_3=c\). Portanto, o conjunto gera \(S_{22}\).
  2. Teste de Independência Linear: Considere a combinação que resulta na matriz nula. Pelo passo anterior, isso implica \(c_1=0, c_2=0, c_3=0\). A única solução é a trivial.
  3. Como o conjunto é LI e gera o espaço, ele é uma base.
Base: LI + Span

Conexão com o Mundo dos Jogos: Definir uma base para um conjunto de "estados" (como matrizes de status) permite que os desenvolvedores armazenem e manipulem esses estados de forma eficiente, usando apenas as coordenadas em vez da matriz inteira.

A Fórmula da Trajetória (Coordenadas em uma Base de Polinômios)

Objetivo da Missão: Calcular as coordenadas de um polinômio em relação a uma base de polinômios.

A trajetória de um projétil é descrita pelo polinômio \(p(t) = 4 + 6t - t^2\). O sistema de controle do projétil usa a base \(B=\{1, t-1, (t-1)^2\}\) para \(P_2\). Encontre as coordenadas de \(p(t)\) nesta base.

Pedir Dica ao Mestre do Jogo...

Expanda os polinômios da base (ex: \((t-1)^2 = t^2-2t+1\)). Em seguida, monte a equação \(c_1(1) + c_2(t-1) + c_3(t-1)^2 = 4+6t-t^2\) e iguale os coeficientes das potências de \(t\).

Ver Detonado...
  1. Monte a equação: \(c_1 + c_2(t-1) + c_3(t^2-2t+1) = 4+6t-t^2\).
  2. Reagrupe o lado esquerdo por potências de \(t\): \(c_3t^2 + (c_2-2c_3)t + (c_1-c_2+c_3) = -t^2+6t+4\).
  3. Iguale os coeficientes correspondentes para formar um sistema linear:
    • \(c_3 = -1\) (coeficientes de \(t^2\))
    • \(c_2-2c_3 = 6\) (coeficientes de \(t\))
    • \(c_1-c_2+c_3 = 4\) (termos constantes)
  4. Resolva o sistema para encontrar \(c_1, c_2, c_3\), que são as coordenadas desejadas.
Igualar coeficientes: \(a_1t^2+... = a_2t^2+... \implies a_1=a_2, ...\)

Conexão com o Mundo dos Jogos: Em animação, usar bases como esta (chamadas de bases de Bernstein em um contexto similar) permite controlar as curvas de forma mais intuitiva. As coordenadas podem representar o ponto inicial, a velocidade inicial e a aceleração em um determinado ponto, em vez dos coeficientes abstratos da base canônica.

Mapeando o Campo de Batalha (Encontrar uma Base para um Plano)

Objetivo da Missão: Dado um plano em \(\mathbb{R}^3\), encontrar um conjunto de vetores que forma uma base para ele.

Um campo de batalha plano é definido pela equação \(x+y-z=0\). Encontre uma base para este subespaço de \(\mathbb{R}^3\).

Pedir Dica ao Mestre do Jogo...

A equação tem 3 variáveis e 1 restrição. Isso significa que há 2 "variáveis livres". Expresse a variável dependente em termos das livres e, em seguida, separe os termos para extrair os vetores da base.

Ver Detonado...
  1. Isole uma variável na equação do plano. Por exemplo, \(z=x+y\).
  2. Um vetor genérico no plano tem a forma \(\vec{v} = (x, y, x+y)\).
  3. Separe o vetor em partes contendo apenas \(x\) e partes contendo apenas \(y\): \(\vec{v} = (x, 0, x) + (0, y, y)\).
  4. Fatore as variáveis livres: \(\vec{v} = x(1, 0, 1) + y(0, 1, 1)\).
  5. Isso mostra que qualquer vetor no plano é uma combinação linear de \(\vec{b_1}=(1,0,1)\) e \(\vec{b_2}=(0,1,1)\). Estes dois vetores geram o plano e são LI. Portanto, formam uma base.
Solução Geral \(\implies\) Vetores da Base

Conexão com o Mundo dos Jogos: Quando se projeta um nível em um terreno plano inclinado, os desenvolvedores definem implicitamente uma base para aquele plano. Os movimentos dos personagens e a colocação de objetos são então calculados em relação a essa base para garantir que permaneçam no chão.

O Arsenal do Time (Base para o Espaço Coluna)

Objetivo da Missão: Praticar o algoritmo para encontrar uma base para o espaço coluna de uma matriz.

Um time de heróis tem 4 habilidades de ataque, representadas pelos vetores coluna da matriz \(A = \begin{pmatrix} 1 & 2 & 3 & 1 \\ 2 & 4 & 7 & 3 \\ 3 & 6 & 10 & 4 \end{pmatrix}\). Encontre um conjunto mínimo de habilidades "fundamentais" que geram todo o seu potencial ofensivo (ou seja, encontre uma base para o espaço coluna de A).

Pedir Dica ao Mestre do Jogo...

Escale a matriz \(A\) para sua forma escalonada. As colunas da matriz *original* que correspondem às colunas com pivôs na matriz escalonada formam a base.

Ver Detonado...
  1. Escale a matriz \(A\) para sua forma escalonada (RREF é ainda melhor).
  2. Identifique as colunas que contêm as posições de pivô (os "1"s líderes de cada linha).
  3. A base para o espaço coluna de \(A\) é o conjunto dos vetores coluna da matriz **original** \(A\) que correspondem a essas posições de pivô.
  4. Nota: As colunas da matriz escalonada *não* formam a base do espaço coluna de \(A\), pois as operações de linha podem alterar o espaço coluna.
Colunas de Pivô na RREF \(\implies\) Colunas Base na Matriz Original

Conexão com o Mundo dos Jogos: Esta técnica permite que os designers analisem um conjunto complexo de habilidades de personagens e identifiquem quais são as "essenciais" e quais são redundantes (combinações das essenciais). Isso é crucial para o balanceamento e para evitar habilidades inúteis.

Os Caminhos Secretos (Base para o Espaço Nulo)

Objetivo da Missão: Praticar o algoritmo para encontrar uma base para o espaço nulo de uma matriz.

Uma transformação de "compressão de dados" \(A = \begin{pmatrix} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{pmatrix}\) envia certos vetores de dados \(\vec{x}\) para \(\vec{0}\). Encontre uma base para o subespaço de todos os vetores \(\vec{x} \in \mathbb{R}^4\) que são "anulados" por esta transformação (ou seja, uma base para o Espaço Nulo de A).

Ver Detonado...
  1. Resolva o sistema homogêneo \(A\vec{x}=\vec{0}\). A matriz \(A\) já está em forma escalonada.
  2. Identifique as variáveis de pivô (correspondentes às colunas de pivô, \(x_1\) e \(x_3\)) e as variáveis livres (as outras, \(x_2\) e \(x_4\)).
  3. Escreva as equações: \(x_1 + 2x_2 + 3x_4 = 0\) e \(x_3 - x_4 = 0\).
  4. Expresse as variáveis de pivô em termos das variáveis livres: \(x_1 = -2x_2 - 3x_4\) e \(x_3 = x_4\).
  5. Escreva o vetor solução genérico \(\vec{x}\) e separe-o em partes, uma para cada variável livre.
  6. \(\vec{x} = \begin{pmatrix} -2x_2 - 3x_4 \\ x_2 \\ x_4 \\ x_4 \end{pmatrix} = x_2\begin{pmatrix}-2\\1\\0\\0\end{pmatrix} + x_4\begin{pmatrix}-3\\0\\1\\1\end{pmatrix}\).
  7. Os vetores que multiplicam as variáveis livres formam a base para o Espaço Nulo.
Solução Geral de \(A\vec{x}=\vec{0}\) \(\implies\) Base do Espaço Nulo

Conexão com o Mundo dos Jogos: Em física de simulação, o Espaço Nulo de uma matriz de restrições representa todos os movimentos que um personagem ou objeto pode fazer sem violar as regras. Por exemplo, em uma simulação de ragdoll, o Espaço Nulo descreve como as partes do corpo podem se mover sem se desconectar umas das outras.

O Sistema de Defesa Ortogonal (Propriedades de Bases Ortogonais)

Objetivo da Missão: Provar que um conjunto de vetores ortogonais não nulos é sempre Linearmente Independente.

Três canhões de defesa estão posicionados em direções mutuamente perpendiculares (ortogonais), dadas pelos vetores não-nulos \(\{\vec{v_1}, \vec{v_2}, \vec{v_3}\}\). Prove que seus vetores de tiro devem ser Linearmente Independentes.

Ver Detonado...
  1. Comece com a equação de teste: \(c_1\vec{v_1} + c_2\vec{v_2} + c_3\vec{v_3} = \vec{0}\).
  2. Para provar que \(c_1=0\), faça o produto escalar de ambos os lados da equação por \(\vec{v_1}\): \(\vec{v_1} \cdot (c_1\vec{v_1} + c_2\vec{v_2} + c_3\vec{v_3}) = \vec{v_1} \cdot \vec{0}\).
  3. Use a linearidade do produto escalar: \(c_1(\vec{v_1}\cdot\vec{v_1}) + c_2(\vec{v_1}\cdot\vec{v_2}) + c_3(\vec{v_1}\cdot\vec{v_3}) = 0\).
  4. Por serem ortogonais, \(\vec{v_1}\cdot\vec{v_2} = 0\) e \(\vec{v_1}\cdot\vec{v_3} = 0\). A equação se simplifica para \(c_1(\vec{v_1}\cdot\vec{v_1}) = 0\).
  5. Como \(\vec{v_1}\) não é nulo, \(\vec{v_1}\cdot\vec{v_1} = ||\vec{v_1}||^2 \neq 0\). Portanto, a única possibilidade é que \(c_1=0\).
  6. Repita o processo, fazendo o produto escalar com \(\vec{v_2}\) e depois com \(\vec{v_3}\), para mostrar que \(c_2=0\) e \(c_3=0\).
  7. Como a única solução é a trivial, o conjunto é Linearmente Independente.
Chave do Puzzle: \(\vec{v_i} \cdot \vec{v_j} = 0\) para \(i \neq j\)

Conexão com o Mundo dos Jogos: Bases ortogonais (e ortonormais) são as melhores "bases GPS". Elas correspondem aos eixos X, Y, Z que usamos intuitivamente. São a fundação para a maioria dos sistemas de coordenadas em física e gráficos de jogos, pois simplificam enormemente os cálculos de distância, rotação e projeção.

Tradução de Mapas (Coordenadas em Duas Bases Diferentes)

Objetivo da Missão: Encontrar as coordenadas de um mesmo vetor em duas bases não-canônicas distintas.

Um ponto de interesse no mapa está em \(\vec{v}=(7,5)\). Duas facções observam este ponto a partir de suas bases:

Encontre as coordenadas do ponto \(\vec{v}\) para cada facção. Ou seja, encontre \([\vec{v}]_A\) e \([\vec{v}]_B\).

Ver Detonado...
  1. Este desafio consiste em resolver dois sistemas lineares independentes.
  2. Para a Facção A: Resolva o sistema \(A\vec{c}_A = \vec{v}\), que é \(\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix} = \begin{pmatrix}7\\5\end{pmatrix}\). A solução lhe dará \([\vec{v}]_A\).
  3. Para a Facção B: Resolva o sistema \(B\vec{c}_B = \vec{v}\), que é \(\begin{pmatrix}2&1\\0&1\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix} = \begin{pmatrix}7\\5\end{pmatrix}\). A solução lhe dará \([\vec{v}]_B\).
  4. Observe que, embora o vetor \(\vec{v}\) seja o mesmo, seus vetores de coordenadas \([\vec{v}]_A\) e \([\vec{v}]_B\) são diferentes, pois são medidos em relação a "réguas" diferentes.
Dois problemas: \(A\vec{c}_A = \vec{v}\) e \(B\vec{c}_B = \vec{v}\)

Conexão com o Mundo dos Jogos: Este é o problema central da "mudança de base". Um motor de jogo precisa constantemente traduzir coordenadas entre diferentes sistemas: coordenadas do mundo, coordenadas locais de um objeto, coordenadas da câmera, coordenadas da tela. Dominar essa tradução é essencial para que os gráficos e a física funcionem corretamente.