Sistema de inventário auto-organizado / inteligente?

Na semana passada, estive trabalhando em um sistema de inventário com o Unity3D. No começo, recebi ajuda dos caras do Design3, mas não demorou muito para dividirmos o caminho, porque eu realmente não gostei da maneira como eles fizeram seu código, não tinha cheiro de OOP.

Eu dei mais alguns passos à frente - os itens ocupam mais de um slot, sistema de posicionamento avançado (os itens tentam o melhor para encontrar o melhor encaixe perfeito), sistema de mouse local (o mouse fica preso na área ativa da bolsa), etc.

Aqui está uma demonstração do meu trabalho.

O que gostaríamos de ter em nosso jogo é um recurso de organização automática - não uma classificação automática. Queremos esse recurso porque nosso inventário será em 'tempo real' - não como em Resident Evil 1,2,3 etc, onde você pausaria o jogo e faria as coisas em seu inventário. Agora imagine-se em uma situação complicada cercada por zumbis, e você não tem balas, olha em volta, vê que há balas por perto, então você as procura e tenta pegá-las, mas elas não caiba! você olha para o seu inventário e descobre que, se você reorganizar alguns dos itens, ele se ajustará! - agora o jogador - nessa situação, não tem tempo para se reorganizar porque está cercado de zumbis e morrerá se parar e organizar o inventário para ganhar espaço (lembre-se do inventário em tempo real, sem pausa) - não faria ' será bom que isso aconteça automaticamente? - Sim!

(Acredito que isso tenha sido implementado em alguns jogos como o Dungeon Siege ou algo assim, com certeza é possível)

dê uma olhada nesta foto, por exemplo:

Sim, se você classificar automaticamente o problema, obterá seus espaços, mas é ruim porque: 1- Caro: não precisa de uma operação de classificação inteira para liberar esses espaços; na primeira foto, basta deslizar o item vermelho no embaixo, à esquerda, e você obtém os mesmos espaços da classificação automática. 2- É irritante para o jogador: "Quem o F disse para você reordenar minhas coisas?"

Eu não estou pedindo "Como escrever o código" para isso, estou apenas pedindo alguma orientação, onde procurar, quais algoritmos estão envolvidos? Isso está relacionado a gráficos e ao caminho mais curto? Espero que não, porque não consegui continuar meus estudos na faculdade: / Mas, mesmo que seja, apenas me diga e vou aprender as coisas relacionadas.

Observe que pode haver mais do que apenas uma solução. Então, acho que a primeira coisa a fazer é descobrir se a situação é 'solucionável' - se eu sei como determinar se uma situação é solucionável ou não, então posso 'resolvê-la'. Eu só preciso conhecer as condições que o tornam 'solucionável'. E acredito que deve haver alguma estrutura de algoritmo / dados para isso.

Aqui está uma foto de mais de uma solução para tentar ajustar um item 1x3:

As setas mostram apenas uma das soluções, mas se você procurar, encontrará mais de uma. É isso que, em última análise, não classifico automaticamente, mas encontro uma solução e a aplico.

Observe que, se eu dedicar um tempo, vou encontrar uma maneira de resolvê-lo, mas não seria o melhor, é como segurar um volante de carro com os pés em vez das mãos! XD Ou apenas tente resolver um problema que requer matrizes, mas você ainda não está ciente da existência delas! Então, qual é a abordagem correta para isso?

Atualizações do comentário

@ Stephen Eu realmente não sou um guru em Alogs, você mencionou 'mochila' e @BlueRaja - Danny Pflughoeft mencionou um item de embalagem em 2D. Eles estão de alguma forma relacionados / iguais? - Ainda estou confuso sobre como devo abordar isso.

E sim, eu já estou usando uma "heurística", mas eu realmente não sabia que estava: D encontra o primeiro slot disponível e vê se o item se encaixa lá.

Não sei se a encomenda de itens com base em sua "granulometria" (que eu chamo de nSlotsRequired = nRowsReq * nColsRec) funcionaria, porque você tem itens 2x2 e 1x4, por exemplo, eles têm a mesma granelidade, mas com formas diferentes e terão um efeito diferente sobre como o restante dos itens a seguir será. ENTÃO... :/

Eu assisti esse vídeo, gostei muito da ideia de embalagem completa, mas me pergunto como proceder, já que o inventário é 2D. Eu nem tenho certeza de que a embalagem da lixeira é a chave aqui porque, bem, é verdade que eu posso ter mais de uma bolsa, mas no nosso jogo, será apenas uma bolsa. Portanto, é uma questão de colocar itens em uma bolsa e não mais do que isso. Portanto, os exemplos nesse vídeo (os canos e os ônibus) realmente não correspondem ao meu problema. Também assisti algumas coisas sobre essa coisa de mochila, não vi como o 'valor' está relacionado aos meus itens / estoque, mas acho que 'peso' é o mesmo que volume, não tenho certeza.

Esta é uma variação do problema da mochila. Como Danny Pflughoeft menciona, é NP-Complete. Significando que não pode ser resolvido em tempo linear, se bem me lembro.

Mas você pode tentar resolver isso em várias etapas. É basicamente um problema de classificação.

Eu começaria calculando o volume de cada item: isso poderia ser calculado de várias maneiras:

• volume = máximo (comprimento, largura);

• volume = comprimento * largura

• volume = sqrt (comprimento * largura)

Em seguida, comece a colocar itens com a pontuação mais alta primeiro no inventário. Uma vez que eles provavelmente não se encaixam no espaço restante mais tarde. Pequenos itens cabem sempre.

Você precisa de uma heurística (um nome sofisticado para adivinhações educadas ;-)) para sua estratégia de colocação. Algo como tentar encaixar itens no primeiro espaço livre do canto superior esquerdo ou algo assim.

A estratégia de classificação de estoque do Diablo II funcionou de maneira semelhante, eu acho. Coisas como espadas e lanças terminariam no canto superior esquerdo, depois roupas e armaduras, depois broquel e assim por diante.

Eu acho que você realmente precisa tentar fazer isso e ajustar o algoritmo (cálculo de volume diferente, heurística diferente), até que funcione bastante.

Haha, @Todo mundo que ajudou, obrigado. Consegui finalmente resolvê-lo. Aqui está o que eu basicamente fiz:

IEnumerator AddItem_Sorted (Item item)

1. Condição trivial: verifique se temos o mínimo nRequiredSlots para o item caber, se o tivermos, prossiga ...
2. esvaziaremos todo o saco - colocando os itens em um espaço reservado (lista ou algo assim)
3. adicione o item desejado ao MUITO último slot / local em que ele pode se encaixar, certificando-se de que tem a forma horizontal
4. usando o algo decrescente de primeiro ajuste, adicionaremos o restante de nossos itens
5. durante a adição, usaremos programação dinâmica (memoisation) para lembrar o índice que estamos adicionando (índice do próximo slot disponível)
6. se toda a adição for bem-sucedida, conseguimos ajustar o item desejado e, de alguma forma, classificar a sacola - de itens grandes a pequenos
7. se não pudéssemos adicionar todos os itens, isso significa que, não era uma situação solucionável, então temos que levar a bolsa ao seu estado anterior
8. uma maneira de fazer isso (saiu da superfície da minha mente) é copiar o estado da bolsa antes de toda essa operação e, se falhar, voltaremos ao estado anterior, ou melhor, durante o ' esvaziando 'o saco, memorizamos onde cada item estava, para que, se o op falhar, os recuperemos - usando AddItem (item, índice) - nos índices anteriores :)
9. todo esse processo pode levar tempo, para que possamos dividir a carga em quadros separados, usando meu rendimento adorável :)
10. FEITO ! \ m / (@ ~ 9:00)

ATUALIZAR:

1. Fiz uma matriz que armazenava os índices de todos os itens adicionados, para que não precisasse procurar os slots ocupados para liberar - grande impulso.

2. não há necessidade de adicionar no último slot; de fato, às vezes, pode não funcionar dessa maneira. Adicionei o item desejado ao restante dos outros itens e os classifiquei com eles.

Como você pode ver no vídeo, ele precisa de um pouco de otimização, a classificação não é perfeita, eu gostaria de usar a embalagem cheia, mas já é um desempenho ganancioso. Estou aberto a sugestões de otimização, obrigado novamente :)