Sistema de inventário auto-organizado / inteligente?

11

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:

O que a classificação automática faz

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:

insira a descrição da imagem aqui

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.

vexe
fonte
7
Trata-se de embalagem em caixote 2D, que é NP-Complete. Portanto, qualquer algoritmo que informe se você pode ajustar todos os itens será ineficiente (na pior das hipóteses). Você pode encontrar alguns algoritmos de aproximação bastante bons.
BlueRaja - Danny Pflughoeft
Foi exatamente por isso que decidi sobre o modelo de inventário do tipo um slot por item (mais comum atualmente) em vez disso. Eu gostaria de ter uma solução para você, eu desisti de este problema ...
Ryno
@ BlueRaja-DannyPflughoeft Gostaria de saber se um algoritmo simples / eficiente está disponível se os itens foram limitados a determinadas formas?
congusbongus
A limitação de formas não reduz a complexidade, mas facilita a reflexão, para que você pense que a complexidade foi resolvida.
Patrick Hughes
@ VeXe Desculpe, perdi a atualização da sua pergunta. Embalagem e mochila não são a mesma coisa. Mas ambos estão com problemas de embalagem. O "valor" no seu caso é a forma e o tamanho dos seus objetos de inventário.
Stephen

Respostas:

8

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.

Stephen
fonte
1
NP-complete é um conjunto de problemas com complexidade maior que o polinômio. Para um inventário relativamente pequeno (menos de mil itens, eu diria :)), mesmo o algoritmo exponencial funcionaria muito rápido, porque uma etapa desse algoritmo leva muito pouco tempo. No entanto usando a sua ideia deve ser bom o suficiente e mais fácil de implementar um algoritmo de programação dinâmica -> 1
MartinTeeVarga
thx para o voto positivo. Sim o inventário não deve ser potencialmente infinito de modo algoritmos exponenciais deve funcionar bem ^^
Stephen
@ sm4: Normalmente, mil é um número enorme de problemas no NP-Complete. Lembre-se, esses problemas são O (2 ^ n) - mesmo apenas 2 ^ 64 é computacionalmente inviável!
BlueRaja - Danny Pflughoeft 31/01
3

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 :)

vexe
fonte
De nada! :) Gostaria de agradecer a BlueRaja - Danny Pflughoeft por mencionar a embalagem, @Stephen pela idéia de volume e Richard Buckland por sua palestra dinâmica de programação e todas as palestras.
vexe 2/07/2017