Push Push

[shaan1974]

Hello all,

Push Push is out

You can get it on Itch io for free => https://crazypiri.itch.io/push-push

This is my first game created with love2d. The concept and mechanics of the game are based on – Puzzle’n desu – of the “Super Nintendo”.

I tried to reproduce the mechanics to run some tests, but it ended up becoming a full game.

It is a puzzle game in which you will have to assemble blocks together to make them disappear.

To push a block, you need to move next to it, select the direction and press “A”.

There will also be special blocks which can be pushed and/or destroyed, and blocks that cannot be moved.

More explanations in manuals. The manuals are availables in English and French.

[darkfrei]

Nice! The second level was too complicated for the first try.

Also here was expected that it counts as exit, but somehow no:

Screenshot 2023-05-09 203225.png (79.12 KiB) Viewed 2483 times

Also please add the Exit to the main menu:

Screenshot 2023-05-09 203342.png (117.19 KiB) Viewed 2483 times

[shaan1974]

I'm gonna tool your remarks for next version.

Solution for the second level

By the way in the youtube video i do the first five level

[darkfrei]

I'm gonna tool your remarks for next version.

Solution for the second level

By the way in the youtube video i do the first five level

I've solved the second level other way, all red to the down side.

[shaan1974]

There are multiples ways to resolve screens

At the beginning i want to create 100 levels but after 50 my brain was burned

[darkfrei]

There are multiples ways to resolve screens

At the beginning i want to create 100 levels but after 50 my brain was burned

Did you tried to make level generator and solve/check it with level solver?

It looks that it can be done with Breadth-First Search with some optimization tricks.
https://en.wikipedia.org/wiki/Breadth-first_search

[shaan1974]

There are multiples ways to resolve screens

At the beginning i want to create 100 levels but after 50 my brain was burned

Did you tried to make level generator and solve/check it with level solver?

It looks that it can be done with Breadth-First Search with some optimization tricks.
https://en.wikipedia.org/wiki/Breadth-first_search

i'm made a small generator in an html page with javascript to create easily the structure

[darkfrei]

The bfs solver with some optimizations, but it needs a lot of time to solve the example:

Code: Select all

-- bfs solver for pushpush

-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------

local function isWayTo (map, x1, y1, x2, y2) -- astar
	local openSet = {}
	local closedHashes = {}
	local nodesGrid = {}
	local neighborSet = {{x=0,y=-1}, {x=1,y=0}, {x=0,y=1}, {x=-1,y=0}}

	local function heuristic(x, y)
		return math.abs (x-x2) + math.abs (y-y2)
	end
	
	local function isFree (map, x, y)
		if map[y] and map[y][x] and map[y][x] == 0 then
			return true
		end
		return false
	end
		
	local function nearestNode (nodes)
		local fMin = math.huge
		local currentIndex = 1
		for i, node in ipairs(nodes) do
			local f = node.f
			if f < fMin then
				fMin = f
				currentIndex = i
			end
		end
		return currentIndex
	end
	
	local function getNeighbors(map, x0, y0)
		local neighbors = {}
		for i, d in ipairs (neighborSet) do
			local x, y = x0+d.x, y0+d.y
			if isFree (map, x, y) then
				local node = nodesGrid[y][x]
				table.insert (neighbors, node)
			end
		end
		return neighbors
	end

	for y = 1, #map do
		nodesGrid[y] = {}
		for x = 1, #map[y] do
			nodesGrid[y][x] = {x=x,y=y}
		end
	end
	
--	print ('nodesGrid', x1, y1)
	local current = nodesGrid[y1][x1]
	current.g = 0
	current.f = heuristic(x1, y1)
	table.insert(openSet, current)

	while #openSet > 0 do
		local currentIndex = nearestNode (openSet)
		current = table.remove (openSet, currentIndex)
		closedHashes[current] = true

		if current.x == x2 and current.y == y2 then
			return true
		end

		local neighbors = getNeighbors(map, current.x, current.y)
		local gScore = current.g + 1
		for _, neighbor in ipairs(neighbors) do
			if not closedHashes[neighbor] then
				neighbor.g = gScore
				neighbor.f = gScore + heuristic(neighbor.x, neighbor.y)
				closedHashes[neighbor] = true
				table.insert(openSet, neighbor)
			end
		end
	end

	return false
end


-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------


local function isFree (map, x, y)
	if map[y] and map[y][x] and map[y][x] == 0 then
		return true
	end
	return false
end

local function getNeighborCells(state, positions, px, py)
--	print ('getNeighborCells', px, py)
	local neighborCells = {}
	local neighborSet = {{x=0,y=-1, dir="U"}, {x=1,y=0, dir="R"}, {x=0,y=1, dir="D"}, {x=-1,y=0, dir="L"}}
	for _, position in ipairs(positions) do -- boxes positions
		local x, y = position.x, position.y
		for _, d in ipairs(neighborSet) do
			local nx, ny = x - d.x, y - d.y -- player position to push the box
			local mx, my = x + d.x, y + d.y -- can move the box
			if isFree (state, nx, ny) and isFree (state, mx, my) then
				if isWayTo (state, px, py, nx, ny) then
					local neighborPosition = {x = x, y = y, dx=d.x, dy=d.y, dir=d.dir}
					table.insert(neighborCells, neighborPosition)
				end
			end
		end
	end
	return neighborCells
end

local function getPlayer (map)
	for y, xs in ipairs (map) do
		for x, value in ipairs (xs) do
			if value == 1 then -- player
				map[y][x] = 0
				return x, y
			end
		end
	end
end



local function getStonePositions (map)
	local positions = {}
	for y, xs in ipairs (map) do
		for x, value in ipairs (xs) do
			if value >= 3 then -- box
				table.insert (positions, {x=x, y=y, value=value})
			end
		end
	end
	return positions
end

local function getBoxPositions (map)
	local positions = {}
	for y, xs in ipairs (map) do
		for x, value in ipairs (xs) do
			if value >= 3 then -- box
				table.insert (positions, {x=x, y=y, value=value})
			end
		end
	end
	return positions
end


local function copyState (state)
	local newState = {}
	for y, xs in ipairs (state) do
		newState[y] = {}
		for x, value in ipairs (xs) do
			newState[y][x] = value
		end
	end
	return newState
end

local function applyChanges(state, changes, px, py)
	local newState = copyState(state)
	
	for i, change in ipairs (changes) do
		if change.remove then
			for i = 1, #change-1, 2 do
				local x1, y1 = change[i], change[i+1]
				newState[y1][x1] = 0
			end
		else -- move from 1 to 2
			local x1,y1, x2, y2 = change[1], change[2], change[3], change[4]
			newState[y2][x2] = newState[y1][x1]
			newState[y1][x1] = 0
			px, py = x1, y1 -- player position is a last one
		end
	end
	return newState, px, py
end

local function targetConditionFunction (state)
	for y, xs in ipairs (state) do
		for x, value in ipairs (xs) do
			if value >=3 then
				return false -- at least one box here
			end
		end
	end
	return true
end

local function pushBox(state, bx1, by1, dx, dy)
	local bx2, by2 = bx1, by1

	while isFree(state, bx2 + dx, by2 + dy) do
		bx2 = bx2 + dx
		by2 = by2 + dy
	end

	return bx1, by1, bx2, by2 
end


local function getChangesFunction(state, px, py)
	local newState = copyState (state)
	
	local boxPositions = getBoxPositions(newState)
	local nCells = getNeighborCells(newState, boxPositions, px, py)
	
	local changes = {}
	for i, nCell in ipairs(nCells) do
		local bx1, by1, bx2, by2 = pushBox(newState, nCell.x, nCell.y, nCell.dx, nCell.dy)
		local change = {bx1, by1, bx2, by2}
		table.insert(changes, change)
	end
	return changes
end

local function copyChanges(changes, newChange)
	local newChanges = {}
	for i, change in ipairs(changes) do
		table.insert(newChanges, change)
	end
	table.insert(newChanges, newChange)
	return newChanges
end

local function getRemovingChange(state)
	local height = #state
	local width = #state[1]
	local removeBoxes = {}
	local hash = {}

	for y = 1, height do
		local currentValue = nil
		local currentCount = 0

		for x = 1, width do
			local boxValue = state[y][x]
			if currentValue == nil and boxValue >=3 then
				currentValue = boxValue
				currentCount = 1
			elseif boxValue == currentValue then
				currentCount = currentCount + 1
			else
				if currentCount >= 3 then
					for x0 = x - currentCount, x - 1 do
						table.insert(removeBoxes, x0)
						table.insert(removeBoxes, y)
						hash[x0..'-'..y] = true
					end
				end
				currentValue = nil
				currentCount = 0
				if boxValue >= 3 then 
					currentValue = boxValue
					currentCount = 1
				end
			end
		end

		if currentCount >= 3 then
			for x0 = width - currentCount + 1, width do
				table.insert(removeBoxes, x0)
				table.insert(removeBoxes, y)
				hash[x0..'-'..y] = true
			end
		end
	end


	
	for x = 1, width do
		local currentValue = nil
		local currentCount = 0

		for y = 1, height do
			local boxValue = state[y][x]
			if currentValue == nil and boxValue >=3 then
				currentValue = boxValue
				currentCount = 1
			elseif boxValue == currentValue then
				currentCount = currentCount + 1
			else
				if currentCount >= 3 then
					for y0 = y - currentCount, y - 1 do
						if not hash[x..'-'..y0] then
							table.insert(removeBoxes, x)
							table.insert(removeBoxes, y0)
						end
					end
				end
				currentValue = nil
				currentCount = 0
				if boxValue >= 3 then 
					currentValue = boxValue
					currentCount = 1
				end
			end
		end

		if currentCount >= 3 then
			for y0 = height - currentCount + 1, height do
				if not hash[x..'-'..y0] then
					table.insert(removeBoxes, x)
					table.insert(removeBoxes, y0)
				end
			end
		end
	end
	
	
	
	if #removeBoxes > 0 then
		for i = 1, #removeBoxes-1, 2 do
			local x, y = removeBoxes[i], removeBoxes[i+1]
			state[y][x] = 0
		end
		removeBoxes.remove = true
		return removeBoxes
	end
end

local function isSolvable(state)
  local numRows = #state
  local numCols = #state[1]
  local boxCounts = {}


  for y = 1, numRows do
    for x = 1, numCols do
      local value = state[y][x]
      if value >= 3 then
				if not boxCounts[value] then 
					boxCounts[value] = 1
				else
					boxCounts[value] = boxCounts[value] + 1
				end
      end
    end
  end

  for i, boxCount in pairs (boxCounts) do
    if boxCount > 0 and boxCount < 3 then
      return false
    end
  end

  return true
end


-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
local function solver (startState) -- bfs
	local px, py = getPlayer (startState)
	
	if not px then 
		print ('no player!')
		return
	end
	local queue = {{}} -- one empty change

	while #queue > 0 do
		local currentChanges = table.remove(queue, 1)
		local currentState, px, py = applyChanges(startState, currentChanges, px, py)

		if targetConditionFunction(currentState) then
			print ('solution found: ', #currentChanges)
			return currentChanges
		end

		local changes = getChangesFunction(currentState, px, py)
		for i, change in ipairs(changes) do
			local newChanges = copyChanges(currentChanges, change)
			local newState = applyChanges(startState, newChanges, px, py)
			local removingChange = getRemovingChange (newState)
			if removingChange then
				table.insert (newChanges, removingChange)
				local solveble = isSolvable(newState)
				if solveble then
					table.insert(queue, 1, newChanges)
				end
			else
				table.insert(queue, newChanges)
			end
		end
	end

	-- Целевое состояние не достигнуто
	print ('no solution')
	return nil
end

-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------


-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------

--[[
0 is free
1 is player
2 is block
3 and higher are boxes
--]]

--local map = {
--	{1,0,3},
--	{0,3,3},
--	{0,0,0},
--}

local map = {
	{1,0,3,0,0,0},
	{0,3,0,3,3,0},
	{0,0,0,0,5,0},
	{0,0,0,0,0,5},
	{0,0,0,0,5,0},
	{0,4,0,4,4,0},
	{0,0,4,0,0,0},
}


local solution = solver (map)
for i, change in ipairs (solution) do
	if change.remove then
		print ('remove', table.concat(change, ', '))
	else
		print (change[1], change[2], change[3], change[4])
	end
end

Code: Select all

solution found: 	11
2	2	2	1
5	3	6	3
5	2	5	1
2	6	2	7
5	5	6	5
remove	6, 3, 6, 4, 6, 5
5	6	5	7
4	6	4	7
remove	2, 7, 3, 7, 4, 7, 5, 7
4	2	4	1
remove	2, 1, 3, 1, 4, 1, 5, 1