Rogue Mud

Rogue Mud
Beta Project
Developer
Theme	Fantasy, hack and slash
Influences	MAngband, TomeNET
Released	2012-04-10
Updated	2012-04-16
Licensing	Open Source, Free to play
P. Language	Python
Platforms	Multiple/ Telnet
Interface	ASCII
Game Length	a coffeebreak length
[ Official site of Rogue Mud]

Rogue Mud is a coffeebreak roguelike

After another attempt to take over the server I am using to host the game I decided to switch it off(until then you can still access it under telnet 84.200.213.25 6023). However, before doing so, I hereby publish the source code behind the game for you to study.

To me implementing the _calculate_line_of_sight function (does what its name tells) and the a_star function (movements of bots/ AI) were the most interesting parts - the rest is (what I think) solid Python code, mainly functional-style and some object oriented-style where it makes sense. Twisted is used heavily under the hood and SQLite is leveraged to persist states. Calculations that can be parallelised are implemented via threads.

Welcome to Rogue Mud

Rogue Mud combines the gameplays of both roguelike [1] games and MUDs [2]. There are a cuple of other examples that already established this - however, those are often full-blown roguelikes. Rogue Mud on the other hand focusses on coffe-break roguelike gameplay, meaning that you can play one game whenever you have 10 minutes of spare time.

Rogue Mud is free to play. You only need a Telnet client and an internet connection.

Bear with me if something goes wrong, I will fix it soon. If you have comments, please add them at the end of this page. There are messages about connection failures that I cannot reconstruct - do you really experience them?

Connect to Rogue Mud

A Telnet client is available on most systems. Use this to connect to the 84.200.213.25 at port 6023, e. g. open a console and type "telnet 84.200.213.25 6023". Character creation etc. is done all over Telnet. If you are using Windows consider Putty [3] as a Telnet client.

Gameplay

The dungeons you play get randomly generated and populated with enemies, items and artefacts. The higher your level is, the bigger the dungeons and mightier the enemies will be.

Every dungeon has exactly one entry ("<") and one exit (">"). Every dungeon is player with four player in a team. These can either be human players with a common level that get randomly assigned to each other or bots depending on your choice. As dungeons become more complex the higher your level is, you need more and more time to find relevant artefacts, get experience, and finally reach the exit. But it should never take you more than about 15 minutes.

To improve your level, you will need to gain experience by fighting enemies and healing allies as well as finding artefacts. As there is only one artefact per dungeon, you need to hurry! Or else somebody besides you will pick it up. Only if you reach the exit of a dungeon you are allowed to keep the artefact. Rogue Mud is a PvE [4]. You cannot do harm to your allies or heal enemies.

Screen and Controls

Field of View

Besides the dungeon's walls ("#"), yourself and the other players ("@") you can only see enemies, items, entries and exits etc. when they are in your field of view. The diameter is determined by your stats and you can either see something on a field (if there is something to be seen) or you see an empty field (".").

Line of Sight

Walls and enemies block your view on whatever might be behind them. Fields you cannot observe behave like fields that are outside of your field of view.

Items and Artifacts

You can pick up items and special items, so called artifacts. They are randomly placed around the dungeon.

Items

Items come in four flavours and are denoted as followed:

• "r" are range items that improve your range stat.
• "s" are speed items that improve your speed stat.
• "v" are view items that improve your view stat.
• "h" are hitpoints items that improve your hitpoints stat.

The effect of items are triggered immediatly after you have picked them up and last for as long you stay in the current dungeon. The effect ceases after you have completed the dungeon or died.

Artifacts

Artefacts are special items. Only one artefact occurs in every dungeon and is randomly placed as well:

• "R" is a range artefact.
• "S" is a speed artefact.
• "V" is a view artefact.
• "H" is a hitpoints artefacts.

If you pick up an artefact first you experience the same effect as with normal items. Only if you manage to complete the dungeon you are allowed to keep and use artfact to improve your stats.

Enemies

Enemies are denoted by single digits. The higher the digits are ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9") the more power the enemies have. They have the same attacking and healing capabilities as you have, so keep an eye on them!

Controls

Walking around

You can walk up, down, left, and right by either using the cursor keys or the vi keys hjkl.

Aiming at Enemies

The keys w and s are used to aim at either the next or previous enemy regarding the distance in your field of view. The enemy will be marked with a "*" if it is the target.

Aiming at Allies

The keys e and d are used to aim at either the next or previous ally regarding the distance in your field of view. The ally will be marked with a "*" if it is the target.

Triggering Actions

After you have targeted an individual (enemy or ally) an action bar starts to fill. Depending on your stats this will take more or less time. When it is full, you can trigger an action on the target you aim at. If the target moved out of your field of view and/ or your range while the action bar filled up, you have to aim again. While the bar is filling up, you are free to walk around.

Individual Action

An individual action is triggered by hitting q. The effect causes an enemy harm (reducing its hitpoints) and is healing and ally (recovering hitpoints up to its current maximum but not exceeding it). The action only effects the single individual that is the target. The farther the individual is away, the lower the effect will be.

Field Action

Hitting a instead triggers a field action. That means depending on your stats the action (attacking enemies or healing allies) is not restricted to one individual but effects potentially several enemies/ allies in a certain range around the targeted individual. The effect on the targeted individual is the highest, decreasing with the distance from that individual. The overall strength of the effect is determined by the distance between the player character and the targeted individual.

Stats, Experience, and Leveling up

Depending on your character stats the game mechanics can be improved in favour of your character. For improving your stats (aka leveling up) you need both experience and artefacts.

Stats

Stats influence your field of view, the capability of targeting individuals, the amount of time that passes by while your action bar fills up and the amount of damage you can take.

Range

The range stat determines how far away an individual might be for you to target it. You can only target an individual if it is both in your range and in your field of view. The range as well determines the strength an effect (decreasing or increasing the hitpoints of enemies or allies) has: The higher the range stat and the less distance between the player character and the targeted individal is, the stronger the effect will be.

Speed

The speed stat determines how fast your action bar fills up. This denotes the time from targeting an individual to triggering an action.

View

The view stat determines the diameter of your field of view. To target an individual it has to be inside of your field of view as well as your range.

Hitpionts

The hitpoints stat determine how much damage you can take. If you hit 0 you lost the dungeon. If you reach the exit of a dungeon with at least 1 hitpoint left you won it.

Experience

You gain experience by both reducing hitpoints of enemies and improving the health of allies. For every hitpoint reduced or recovered you earn one experience point.

Leveling Up

You can improve your stats if two conditions hold true:

• You have at least one artefact of the stat's kind.
• You have suffiecient experience points to spend.

While you need exactly one corresponding artefact every time you improve a stat, the amount of experience needed increases with the level of that stat. Therefore, you need more and more experience to increase a stat further.

Your overall level is the mean of your four stats' levels.

About

Combining Roguelikes and MUDs

One of the major characteristics of roguelikes is that they are not played in real time: Only if you move the world around you will change. To be able to combine the gameplay of roguelikes with a MUD you have to sacrifice this characteristic in favour of "a global clock" that dictates the steps the world changes its states.

You decide: This way you either combine the best of both worlds or the worst. ;)

Sites worth visiting

This project was heavily inspired by the following sites:

• The field of view algorithm Rogue Mud uses is an implementation of this algorithm [5].
• Mangband [6] and TomeNET [7] are two other approaches to combine roguelikes and MUDs.
• RogueBasin is a great source for everything that has to do with roguelikes. But you know that already.

Comments

Please add comments here:

• I would be more tempted to play if there was a genuine software client rather than just telnetting in.

   Mort432 19:18, 13 April 2012 (CEST)

Interesting! I always felt that the simplicity of telnetting in is one of the most appealing features of MUDs ... I will give this some thought.

• User:RylandAlmanza: I agree that telnetting is better than a client. This way you can join in from a remote server or something without downloading anything.
• ...
• ...

Source Code

#!/usr/bin/python
# vim: set fileencoding=utf-8:

import datetime, hashlib, heapq, math, random, time, sqlite3, threading
import twisted.application.internet
import twisted.application.service
import twisted.conch.insults.helper
import twisted.conch.insults.insults
import twisted.conch.insults.text 
import twisted.conch.telnet
import twisted.internet.protocol
import twisted.internet.reactor

class Tile:
	def __init__(self, x, y, character):
		self.x = x
		self.y = y
		self.character = character
class Wall(Tile): pass
class Item(Tile):
	def __init__(self, type, x, y):
		Tile.__init__(self, x, y, '')
		self.type = type
		self.character = {'range': 'r', 'speed': 's', 'view': 'v', 'hitpoints': 'h'}[type]
class Artefact(Item):
	def __init__(self, type, x, y):
		Item.__init__(self, type, x, y)
		self.character = {'range': 'R', 'speed': 'S', 'view': 'V', 'hitpoints': 'H'}[type]
class Entry(Tile): pass
class Exit(Tile): pass
class Individual(Tile):
	def __init__(self, range, speed, view, hitpoints, x, y, character):
		Tile.__init__(self, x, y, character)
		self.range = range
		self.speed = speed
		self.view = view
		self.hitpoints = hitpoints
		self.target = None
		self.charge = 10
		self.action = None
		self.max_range = range
		self.max_speed = speed
		self.max_view = view
		self.max_hitpoints = hitpoints
	def evaluate_action(self, game):
		experience = 0
		distance = ((self.x - self.target.x) ** 2 + (self.y - self.target.y) ** 2) ** .5
		if distance <= self.range and (self.target.x, self.target.y) in game.calculate_line_of_sight(self.x, self.y, self.target.x, self.target.y):
			if self.action == 'individual':
				if self in game.players and self.target in game.players:
					hitpoints = self.target.hitpoints
					self.target.hitpoints += self.range / distance
					self.target.hitpoints = min(self.target.hitpoints, self.target.max_hitpoints)
					experience = self.target.hitpoints - hitpoints
				elif self in game.players and self.target in game.enemies:
					hitpoints = self.target.hitpoints
					self.target.hitpoints -= self.range / distance
					experience = hitpoints - max(0, self.target.hitpoints)
				elif self in game.enemies and self.target in game.enemies:
					self.target.hitpoints += self.range / distance
					self.target.hitpoints = min(self.target.hitpoints, self.target.max_hitpoints)
				elif self in game.enemies and self.target in game.players:
					self.target.hitpoints -= self.range / distance
			elif self.action == 'field':
				remaining_range = self.range - distance
				if self in game.players and self.target in game.players:
					for player, distance_ in [(player, distance_) for player, distance_ in [(player, ((player.x - self.target.x) ** 2 + (player.y - self.target.y) ** 2) ** .5) for player in game.players] if distance_ < remaining_range and not self.target == player and (player.x, player.y) in game.calculate_line_of_sight(self.target.x, self.target.y, player.x, player.y)] + [(self.target, .0)]:
						hitpoints = player.hitpoints
						player.hitpoints += remaining_range / (distance + distance_)
						player.hitpoints = min(player.hitpoints, player.max_hitpoints)
						experience += player.hitpoints - hitpoints
				elif self in game.players and self.target in game.enemies:
					for enemy, distance_ in [(enemy, distance_) for enemy, distance_ in [(enemy, ((enemy.x - self.target.x) ** 2 + (enemy.y - self.target.y) ** 2) ** .5) for enemy in game.enemies] if distance_ < remaining_range and not self.target == enemy and (enemy.x, enemy.y) in game.calculate_line_of_sight(self.target.x, self.target.y, enemy.x, enemy.y)] + [(self.target, .0)]:
						hitpoints = enemy.hitpoints
						enemy.hitpoints -= remaining_range / (distance + distance_)
						experience += hitpoints - max(0, enemy.hitpoints)
				elif self in game.enemies and self.target in game.enemies:
					for enemy, distance_ in [(enemy, distance_) for enemy, distance_ in [(enemy, ((enemy.x - self.target.x) ** 2 + (enemy.y - self.target.y) ** 2) ** .5) for enemy in game.enemies] if distance_ < remaining_range and not self.target == enemy and (enemy.x, enemy.y) in game.calculate_line_of_sight(self.target.x, self.target.y, enemy.x, enemy.y)] + [(self.target, .0)]:
						enemy.hitpoints += remaining_range / (distance + distance_)
						enemy.hitpoints = min(enemy.hitpoints, enemy.max_hitpoints)
				elif self in game.enemies and self.target in game.players:
					for player, distance_ in [(player, distance_) for player, distance_ in [(player, ((player.x - self.target.x) ** 2 + (player.y - self.target.y) ** 2) ** .5) for player in game.players] if distance_ < remaining_range and not self.target == player and (player.x, player.y) in game.calculate_line_of_sight(self.target.x, self.target.y, player.x, player.y)] + [(self.target, .0)]:
						player.hitpoints -= remaining_range / (distance + distance_)
		self.target = None
		self.charge = 10
		return experience
class Enemy(Individual): pass
class Player(Individual):
	offset_range = 2
	offset_speed = 1
	offset_view = 4
	offset_hitpoints = 8
	def __init__(self, name='', password='', experience=0, range_artefact=0, speed_artefact=0, view_artefact=0, hitpoints_artefact=0, range=2, speed=1, view=4, hitpoints=8, x=0, y=0, character='@'):
		Individual.__init__(self, range, speed, view, hitpoints, x, y, character)
		self.name = name
		self.password = password
		self.experience = experience
		self.range_artefact = range_artefact
		self.speed_artefact = speed_artefact
		self.view_artefact = view_artefact
		self.hitpoints_artefact = hitpoints_artefact
	def get_level(self):
		return int(1 + ((self.range - Player.offset_range + self.speed - Player.offset_speed + self.view - Player.offset_view + self.hitpoints - Player.offset_hitpoints) / 4))
	def evaluate_effect(self, game):
		for item in [item for item in game.map[self.x][self.y] if isinstance(item, Item)]:
			if item.type == 'range': self.range += 1
			elif item.type == 'speed': self.speed += 1
			elif item.type == 'view': self.view += 1
			elif item.type == 'hitpoints':
				self.hitpoints = self.max_hitpoints
				self.hitpoints += 1
			if isinstance(item, Artefact):
				if item.type == 'range': self.range_artefact += 1
				elif item.type == 'speed': self.speed_artefact += 1
				elif item.type == 'view': self.view_artefact += 1
				elif item.type == 'hitpoints': self.hitpoints_artefact += 1
			with game.map_lock:
				game.map[self.x][self.y].pop(game.map[self.x][self.y].index(item))
				with game.items_lock:
					game.items.pop(game.items.index(item))
	def experience_used(self):
		return ((self.max_range - Player.offset_range) ** 2) * 10 + ((self.max_speed - Player.offset_speed) ** 2) * 10 + ((self.max_view - Player.offset_view) ** 2) * 10 + ((self.max_hitpoints - Player.offset_hitpoints) ** 2) * 10
	def range_updateable(self):
		experience_needed = ((self.max_range + 1 - Player.offset_range) ** 2) * 10 - ((self.max_range - Player.offset_range) ** 2) * 10
		return (self.range_artefact and self.experience - self.experience_used() > experience_needed and not self.max_range > 10 + Player.offset_range, self.range_artefact, self.experience - self.experience_used() - experience_needed)
	def speed_updateable(self):
		experience_needed = ((self.max_speed + 1 - Player.offset_speed) ** 2) * 10 - ((self.max_speed - Player.offset_speed) ** 2) * 10
		return (self.speed_artefact and self.experience - self.experience_used() > experience_needed and not self.max_speed > 10 + Player.offset_speed, self.speed_artefact, self.experience - self.experience_used() - experience_needed)
	def view_updateable(self):
		experience_needed = ((self.max_view + 1 - Player.offset_view) ** 2) * 10 - ((self.max_view - Player.offset_view) ** 2) * 10
		return (self.view_artefact and self.experience - self.experience_used() > experience_needed and not self.max_view > 10 + Player.offset_view, self.view_artefact, self.experience - self.experience_used() - experience_needed)
	def hitpoints_updateable(self):
		experience_needed = ((self.max_hitpoints + 1 - Player.offset_hitpoints) ** 2) * 10 - ((self.max_hitpoints - Player.offset_hitpoints) ** 2) * 10
		return (self.hitpoints_artefact and self.experience - self.experience_used() > experience_needed and not self.max_hitpoints > 10 + Player.offset_hitpoints, self.hitpoints_artefact, self.experience - self.experience_used() - experience_needed)
	def update_range(self, protocol):
		if self.range_updateable()[0]:
			self.range_artefact -= 1
			self.max_range += 1
			with protocol.factory.connection:
				protocol.factory.connection.execute('update player set range_artefact = ?, range = ? where name = ?', (self.range_artefact, self.max_range, self.name))
	def update_speed(self, protocol):
		if self.speed_updateable()[0]:
			self.speed_artefact -= 1
			self.max_speed += 1
			with protocol.factory.connection:
				protocol.factory.connection.execute('update player set speed_artefact = ?, speed = ? where name = ?', (self.speed_artefact, self.max_speed, self.name))
	def update_view(self, protocol):
		if self.view_updateable()[0]:
			self.view_artefact -= 1
			self.max_view += 1
			with protocol.factory.connection:
				protocol.factory.connection.execute('update player set view_artefact = ?, view = ? where name = ?', (self.view_artefact, self.max_view, self.name))
	def update_hitpoints(self, protocol):
		if self.hitpoints_updateable()[0]:
			self.hitpoints_artefact -= 1
			self.max_hitpoints += 1
			with protocol.factory.connection:
				protocol.factory.connection.execute('update player set hitpoints_artefact = ?, hitpoints = ? where name = ?', (self.hitpoints_artefact, self.max_hitpoints, self.name))

def create_dungeon(x, y, width, height, depth=2, walls=None, rooms=None, split=''):
	if walls is None: walls = []
	if rooms is None: rooms = []
	if depth:
		diff_x_1 = random.choice(range(2, 4))
		diff_x_2 = random.choice(range(2, 4))
		diff_y_1 = random.choice(range(2, 4))
		diff_y_2 = random.choice(range(2, 4))
		if random.random() < .5: # vertical split
			create_dungeon(x + diff_x_1, y + diff_y_1, width / 2 - 2 * diff_x_1, height - 2 * diff_y_1, depth - 1, walls, rooms, split)
			create_dungeon(x + width / 2 + diff_x_2, y + diff_y_2, width / 2 - 2 * diff_x_2, height - 2 * diff_y_2, depth - 1, walls, rooms, 'v')
			return (rooms, walls)
		else: # horizontal split
			create_dungeon(x + diff_x_1, y + diff_y_1, width - 2 * diff_x_1, height / 2 - 2 * diff_y_1, depth - 1, walls, rooms, split)
			create_dungeon(x + diff_x_2, y + height / 2 + diff_y_2, width - 2 * diff_x_2, height / 2 - 2 * diff_y_2, depth - 1, walls, rooms, 'h')
			return (rooms, walls)
	else:
		walls.extend([Wall(x + i, y, '#') for i in range(width)])
		walls.extend([Wall(x + i, y + height - 1, '#') for i in range(width)])
		walls.extend([Wall(x, y + j, '#') for j in range(height)])
		walls.extend([Wall(x + width - 1, y + j, '#') for j in range(height)])
		rooms.extend([(x, y, width, height)])
		if split == 'v':
			begin_x = rooms[-2][0] + rooms[-2][2]
			begin_y = rooms[-2][1] + rooms[-2][3] / 2
			end_x = rooms[-1][0]
			end_y = rooms[-1][1] + rooms[-1][3] / 2
			vertical_x = begin_x + (end_x - begin_x) / 2
			path = [(path_x, begin_y) for path_x in range(begin_x, vertical_x)]
			path += [(path_x, end_y) for path_x in range(vertical_x, end_x)]
			path += [(vertical_x, path_y) for path_y in range(end_y, begin_y + 1)]
			path += [(vertical_x, path_y) for path_y in range(begin_y, end_y + 1)]
			walls.extend([Wall(x + 1, y, '#') for (x, y) in path if not (x + 1, y) in path])
			walls.extend([Wall(x + 1, y + 1, '#') for (x, y) in path if not (x + 1, y + 1) in path])
			walls.extend([Wall(x, y + 1, '#') for (x, y) in path if not (x, y + 1) in path])
			walls.extend([Wall(x - 1, y, '#') for (x, y) in path if not (x - 1, y) in path])
			walls.extend([Wall(x - 1, y - 1, '#') for (x, y) in path if not (x - 1, y - 1) in path])
			walls.extend([Wall(x, y - 1, '#') for (x, y) in path if not (x, y - 1) in path])
			walls.extend([Wall(x + 1, y - 1, '#') for (x, y) in path if not (x + 1, y - 1) in path])
			walls.extend([Wall(x - 1, y + 1, '#') for (x, y) in path if not (x - 1, y + 1) in path])
			[walls.pop(walls.index(wall)) for wall in walls if ((wall.x == begin_x - 1 and wall.y == begin_y) or (wall.x == end_x and wall.y == end_y))]
		elif split == 'h':
			begin_x = rooms[-2][0] + rooms[-2][2] / 2
			begin_y = rooms[-2][1] + rooms[-2][3]
			end_x = rooms[-1][0] + rooms[-1][2] / 2
			end_y = rooms[-1][1]
			horizontal_y = begin_y + (end_y - begin_y) / 2
			path = [(begin_x, path_y) for path_y in range(begin_y, horizontal_y)]
			path += [(end_x, path_y) for path_y in range(horizontal_y, end_y)]
			path += [(path_x, horizontal_y) for path_x in range(end_x, begin_x + 1)]
			path += [(path_x, horizontal_y) for path_x in range(begin_x, end_x + 1)]
			walls.extend([Wall(x + 1, y, '#') for (x, y) in path if not (x + 1, y) in path])
			walls.extend([Wall(x + 1, y + 1, '#') for (x, y) in path if not (x + 1, y + 1) in path])
			walls.extend([Wall(x, y + 1, '#') for (x, y) in path if not (x, y + 1) in path])
			walls.extend([Wall(x - 1, y, '#') for (x, y) in path if not (x - 1, y) in path])
			walls.extend([Wall(x - 1, y - 1, '#') for (x, y) in path if not (x - 1, y - 1) in path])
			walls.extend([Wall(x, y - 1, '#') for (x, y) in path if not (x, y - 1) in path])
			walls.extend([Wall(x + 1, y - 1, '#') for (x, y) in path if not (x + 1, y - 1) in path])
			walls.extend([Wall(x - 1, y + 1, '#') for (x, y) in path if not (x - 1, y + 1) in path])
			[walls.pop(walls.index(wall)) for wall in walls if ((wall.x == begin_x and wall.y == begin_y - 1) or (wall.x == end_x and wall.y == end_y))]
def setup_dungeon(rooms, players, level):
	for i in range(4 - len(players)): players.extend([Player('Bot' + str(i + 1))])
	players[0].x = rooms[0][0] + rooms[0][2] / 2 - 1
	players[0].y = rooms[0][1] + rooms[0][3] / 2 - 1
	players[1].x = rooms[0][0] + rooms[0][2] / 2 - 1
	players[1].y = rooms[0][1] + rooms[0][3] / 2 + 1
	players[2].x = rooms[0][0] + rooms[0][2] / 2 + 1
	players[2].y = rooms[0][1] + rooms[0][3] / 2 - 1
	players[3].x = rooms[0][0] + rooms[0][2] / 2 + 1
	players[3].y = rooms[0][1] + rooms[0][3] / 2 + 1
	enemies = [Enemy((level + Player.offset_range) / 2, (level + Player.offset_speed) / 2, (level + Player.offset_view) / 2, (level + Player.offset_hitpoints) / 2, room[0] + max(room[2] / 4, 1), room[1] + max(room[3] / 4, 1), str(level - 1)) for room in rooms] + [Enemy((level + Player.offset_range) / 2, (level + Player.offset_speed) / 2, (level + Player.offset_view) / 2, (level + Player.offset_hitpoints) / 2, room[0] + room[2] - max(room[2] / 4, 2), room[1] + max(room[3] / 4, 1), str(level - 1)) for room in rooms] + [Enemy((level + Player.offset_range) / 2, (level + Player.offset_speed) / 2, (level + Player.offset_view) / 2, (level + Player.offset_hitpoints) / 2, room[0] + max(room[2] / 4, 1), room[1] + room[3] - max(room[3] / 4, 2), str(level - 1)) for room in rooms] + [Enemy((level + Player.offset_range) / 2, (level + Player.offset_speed) / 2, (level + Player.offset_view) / 2, (level + Player.offset_hitpoints) / 2, room[0] + room[2] - max(room[2] / 4, 2), room[1] + room[3] - max(room[3] / 4, 2), str(level - 1)) for room in rooms]
	items = [Item(random.choice(['range', 'speed', 'view', 'hitpoints']), room[0] + 1 + int((room[2] - 3) * random.random()), room[1] + 1 + int((room[3] - 3) * random.random())) for room in rooms]
	items += [Artefact(random.choice(['range', 'speed', 'view', 'hitpoints']), room[0] + 1 + int((room[2] - 3) * random.random()), room[1] + 1 + int((room[3] - 3) * random.random())) for room in [random.choice(rooms)]]
	entry = Entry(rooms[0][0] + rooms[0][2] / 2, rooms[0][1] + rooms[0][3] / 2, '<')
	exit = Exit(rooms[len(rooms) - 1][0] + rooms[len(rooms) - 1][2] / 2, rooms[len(rooms) - 1][1] + rooms[len(rooms) - 1][3] / 2, '>')
	return (players, enemies, items, entry, exit)

def create_map(tiles):
	map = [[[] for y in range(max([tile.y for tile in tiles]) + 1)] for x in range(max([tile.x for tile in tiles]) + 1)] 
	for tile in tiles: map[tile.x][tile.y].extend([tile])
	return map
def update_map(map, tile, dx, dy):
	map[tile.x][tile.y].pop(map[tile.x][tile.y].index(tile))
	map[tile.x + dx][tile.y + dy].extend([tile])

def line(x0, y0, x1, y1): # Bresenham's line algorithm: only first quadrant, only 0 <= slope <= 1
	dx = x1 - x0
	dy = y1 - y0
	e = dx / 2
	y = y0
	for x in range(x0, x1 + 1):
		yield (x, y)
		e -= dy
		if e < 0:
			y += 1
			e += dx
def a_star(start_node, goal_node, blocked_nodes, abort):
	# node: (x, y)
	def expand_node(current_node, open_list, closed_list, g_map, predecessor_map, blocked_nodes):
		for successor in [node for node in [(current_node[0] + 1, current_node[1]), (current_node[0] - 1, current_node[1]), (current_node[0], current_node[1] + 1), (current_node[0], current_node[1] - 1)] if node not in blocked_nodes]:
			if successor in closed_list: continue
			tentative_g = g_map[current_node] + 1 # c(current_node, successor) = 1
			if successor in [node for costs, node in open_list] and tentative_g >= g_map[successor]: continue
			predecessor_map[successor] = current_node
			g_map[successor] = tentative_g
			f = tentative_g + (((current_node[0] - goal_node[0]) ** 2 + (current_node[1] - goal_node[1]) ** 2) ** .5) # heuristic costs
			index = -1
			for i in range(len(open_list)):
				if open_list[i][1] == successor:
					index = i
					break
			if index > -1:
				open_list.pop(index)
				heapq.heappush(open_list, (f, successor))
			else:
				heapq.heappush(open_list, (f, successor))
	# closed_list: [node]
	closed_list = []
	# open_list (heap): [(f(node), node)]
	open_list = []
	# g_map: {node: g(node)}
	g_map = {}
	# predecessor_map: {node: node}
	predecessor_map = {}
	heapq.heappush(open_list, (0, (start_node[0], start_node[1])))
	g_map[(start_node[0], start_node[1])] = 0
	while open_list:
		current_node = heapq.heappop(open_list)[1]
		if current_node == goal_node:
			path = []
			node = current_node
			while node in predecessor_map:
				path.extend([node])
				node = predecessor_map[node]
			return path
		expand_node(current_node, open_list, closed_list, g_map, predecessor_map, blocked_nodes)
		closed_list.extend([current_node])
		if not len(closed_list) < abort: return [] # Abort if solution is too complex.
	return []

class Bot(threading.Thread):
	def __init__(self, individual, game, break_off, action_map):
		threading.Thread.__init__(self)
		self.individual = individual
		self.game = game
		self.break_off = break_off
		self.action_map = action_map
	def run(self):
		current_time = 0
		while eval(self.break_off):
			time.sleep(max(.125, .5 - (time.time() - current_time)))
			#time.sleep(2)
			current_time = time.time()
			for pair in self.action_map:
				if eval(pair[0]):
					if pair[1]: eval(pair[1])
					break
		with self.game.map_lock:
			self.game.map[self.individual.x][self.individual.y].pop(self.game.map[self.individual.x][self.individual.y].index(self.individual))
			if self.individual in self.game.players:
				with self.game.players_lock: self.game.players.pop(self.game.players.index(self.individual))
			if self.individual in self.game.enemies:
				with self.game.enemies_lock: self.game.enemies.pop(self.game.enemies.index(self.individual))
			with self.game.players_lock:
				for player in self.game.players:
					if player.target == self.individual:
						player.target = None
			with self.game.enemies_lock:
				for enemy in self.game.enemies:
					if enemy.target == self.individual:
						enemy.target = None
	def reach_position(self, x, y, max_depth=8):
		abort = 8
		while not abort > max_depth:
			with self.game.map_lock: 
				path = a_star((self.individual.x, self.individual.y), (x, y), [(tile.x, tile.y) for tile in self.game.walls + self.game.players + self.game.enemies], abort)
				if path:
					step = path.pop()
					dx = step[0] - self.individual.x
					dy = step[1] - self.individual.y
					update_map(self.game.map, self.individual, dx, dy)
					self.individual.x += dx
					self.individual.y += dy
					break
			with self.game.map_lock: 
				path = a_star((self.individual.x, self.individual.y), (x, y), [(tile.x, tile.y) for tile in self.game.walls], abort)
				if path:
					step = path.pop()
					dx = step[0] - self.individual.x
					dy = step[1] - self.individual.y
					if not [tile for tile in self.game.map[self.individual.x + dx][self.individual.y + dy] if isinstance(tile, Player) or isinstance(tile, Enemy)]:
						update_map(self.game.map, self.individual, dx, dy)
						self.individual.x += dx
						self.individual.y += dy
					break
			abort *= 2
	def target_enemy(self, action):
		if self.individual in self.game.players:
			with self.game.enemies_lock:
				enemies = [(enemy, distance) for enemy, distance in [(enemy, ((self.individual.x - enemy.x) ** 2 + (self.individual.y - enemy.y) ** 2) ** .5) for enemy in self.game.enemies] if not distance > self.individual.view and not distance > self.individual.range and (enemy.x, enemy.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, enemy.x, enemy.y)]
				if enemies:
					self.individual.target = sorted(enemies, key=lambda enemy_distance: enemy_distance[1])[0][0]
					self.individual.action = action
			return self.individual.target
		elif self.individual in self.game.enemies:
			with self.game.players_lock:
				players = [(player, distance) for player, distance in [(player, ((self.individual.x - player.x) ** 2 + (self.individual.y - player.y) ** 2) ** .5) for player in self.game.players] if not distance > self.individual.view and not distance > self.individual.range and (player.x, player.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, player.x, player.y)]
				if players:
					self.individual.target = sorted(players, key=lambda player_distance: player_distance[1])[0][0]
					self.individual.action = action
			return self.individual.target
	def target_ally(self, action):
		if self.individual in self.game.players:
			with self.game.players_lock:
				players = [(player, distance) for player, distance in [(player, ((self.individual.x - player.x) ** 2 + (self.individual.y - player.y) ** 2) ** .5) for player in self.game.players if not player == self.individual] if not distance > self.individual.view and not distance > self.individual.range and (player.x, player.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, player.x, player.y) and player.hitpoints < player.max_hitpoints]
				if players:
					self.individual.target = sorted(players, key=lambda player_distance: player_distance[1])[0][0]
					self.individual.action = action
			return self.individual.target
		elif self.individual in self.game.enemies:
			with self.game.enemies_lock:
				enemies = [(enemy, distance) for enemy, distance in [(enemy, ((self.individual.x - enemy.x) ** 2 + (self.individual.y - enemy.y) ** 2) ** .5) for enemy in self.game.enemies if not enemy == self.individual] if not distance > self.individual.view and not distance > self.individual.range and (enemy.x, enemy.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, enemy.x, enemy.y) and not enemy.hitpoints == enemy.max_hitpoints]
				if enemies:
					self.individual.target = sorted(enemies, key=lambda enemy_distance: enemy_distance[1])[0][0]
					self.individual.action = action
			return self.individual.target
	def charge(self):
		if not (self.individual.target in self.game.players + self.game.enemies and ((self.individual.x - self.individual.target.x) ** 2 + (self.individual.y - self.individual.target.y) ** 2) ** .5 <= self.individual.range and (self.individual.target.x, self.individual.target.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, self.individual.target.x, self.individual.target.y)):
			self.individual.target = None
			self.individual.charge = 10
		elif self.individual.charge > 0:
			self.individual.charge -= self.individual.speed
			self.reach_position(self.individual.target.x, self.individual.target.y, max_depth=2 ** 31 - 1)
		else:
			self.individual.evaluate_action(self.game)
class PlayerBot(Bot):
	def __init__(self, individual, game, break_off, action_map, path):
		Bot.__init__(self, individual, game, break_off, action_map)
		self.path = path
		self.step = 0
	def reach_item(self):
		self.individual.evaluate_effect(self.game)
		items = [(item, distance) for item, distance in [(item, ((self.individual.x - item.x) ** 2 + (self.individual.y - item.y) ** 2) ** .5) for item in self.game.items] if not distance > self.individual.view and (item.x, item.y) in self.game.calculate_line_of_sight(self.individual.x, self.individual.y, item.x, item.y)]
		if items:
			item = sorted(items, key=lambda item_distance: item_distance[1])[0][0]
			self.reach_position(item.x, item.y, max_depth=2 ** 31 - 1)
		return items
	def reach_exit(self):
		self.reach_position(self.path[self.step][0], self.path[self.step][1], max_depth=2 ** 31 - 1)
		if ((self.individual.x - self.path[self.step][0]) ** 2 + (self.individual.y - self.path[self.step][1]) ** 2) ** .5 < 4 and self.step < len(self.path) - 1: self.step += 1
class EnemyBot(Bot):
	def __init__(self, individual, game, break_off, action_map):
		Bot.__init__(self, individual, game, break_off, action_map)
		self.flags = [False, False]
		self.current_room = [room for room in self.game.rooms if self.individual.x > room[0] and self.individual.x < room[0] + room[2] - 1 and self.individual.y > room[1] and self.individual.y < room[1] + room[3] - 1][0]
		self.next_room_index = -1
		self.path = []
		self.step = 0
	def walk_around(self):
		current_room_candidates = [room for room in self.game.rooms if self.individual.x > room[0] and self.individual.x < room[0] + room[2] - 1 and self.individual.y > room[1] and self.individual.y < room[1] + room[3] - 1]
		if current_room_candidates: self.current_room = current_room_candidates[0]
		x = self.individual.x + random.choice([-1, 0, 1])
		x = max(x, self.current_room[0] + 1)
		x = min(x, self.current_room[0] + self.current_room[2] - 2)
		y = self.individual.y + random.choice([-1, 0, 1])
		y = max(y, self.current_room[1] + 1)
		y = min(y, self.current_room[1] + self.current_room[3] - 2)
		self.reach_position(x, y)
	def reach_next_room(self):
		if self.step < len(self.path):
			self.reach_position(self.path[self.step][0], self.path[self.step][1], max_depth=2 ** 31 - 1)
			if ((self.individual.x - self.path[self.step][0]) ** 2 + (self.individual.y - self.path[self.step][1]) ** 2) ** .5 < 4 and self.step < len(self.path): self.step += 1
		else:
			current_room_candidates = [room for room in self.game.rooms if self.individual.x > room[0] and self.individual.x < room[0] + room[2] - 1 and self.individual.y > room[1] and self.individual.y < room[1] + room[3] - 1]
			if current_room_candidates: self.current_room = current_room_candidates[0]
			if self.game.rooms.index(self.current_room) == self.next_room_index:
				for i in range(len(self.flags)):
					if not self.flags[i]:
						self.flags[i] = True
						self.next_room_index = -1
						return
			self.next_room_index = min(self.game.rooms.index(self.current_room) + 1, len(self.game.rooms) - 1)
			if self.game.rooms.index(self.current_room) == self.next_room_index: return # already in last room!
			x, y = (self.game.rooms[self.next_room_index][0] + self.game.rooms[self.next_room_index][2] / 2, self.game.rooms[self.next_room_index][1] + self.game.rooms[self.next_room_index][3] / 2)
			self.path = a_star((self.individual.x, self.individual.y), (x, y), [(tile.x, tile.y) for tile in self.game.walls], 2 ** 31 - 1)
			self.path.reverse()
			self.step = 0

class State:
	def process_keystrokeReceived(self, keyID, modifier, protocol): pass
	def render(self, protocol): pass
class Login(State):
	def __init__(self, protocol):
		self.choice = ''
		self.name = ''
		self.password = ''
		self.password_repeated = ''
		self.state = 'get_new_recurring'
	def process_keystrokeReceived(self, keyID, modifier, protocol):
		if self.state == 'get_new_recurring':
			if str(keyID).isalnum(): self.choice += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.choice = self.choice[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if self.choice == 'y':
					self.state = 'recurring_get_name'
				elif self.choice == 'n':
					self.state = 'new_get_name'
				self.choice = ''
		elif self.state == 'new_get_name':
			if str(keyID).isalnum(): self.name += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.name = self.name[0:-1]
			elif (keyID == '\r' or keyID == '\n') and self.name:
				with protocol.factory.connection:
					if protocol.factory.connection.execute('select * from player where name = ?', (self.name, )).fetchone():
						self.state = 'name_already_taken'
					else:
						self.state = 'new_get_password'
		elif self.state == 'name_already_taken':
			if keyID == '\r' or keyID == '\n':
				self.name = ''
				self.state = 'new_get_name'
		elif self.state == 'new_get_password':
			if str(keyID).isalnum(): self.password += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.password = self.password[0:-1]
			elif keyID == '\r' or keyID == '\n':
				self.state = 'repeat_password'
		elif self.state == 'repeat_password':
			if str(keyID).isalnum(): self.password_repeated += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.password_repeated = self.password_repeated[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if self.password == self.password_repeated:
					with protocol.factory.connection:
						protocol.factory.connection.execute('insert into player (name, password, experience, range_artefact, speed_artefact, view_artefact, hitpoints_artefact, range, speed, view, hitpoints) values (?, ?, 0, 0, 0, 0, 0, ?, ?, ?, ?)', (self.name, hashlib.sha256(self.password).hexdigest(), Player.offset_range, Player.offset_speed, Player.offset_view, Player.offset_hitpoints))
					player = Player(self.name, self.password)
					protocol.player = player
					protocol.terminal.eraseDisplay()
					with protocol.factory.connection:
						protocol.factory.connection.execute('insert into login (name, login) values (?, ?)', (protocol.player.name, datetime.datetime.now()))
					print protocol.player.name + ' logged in.'
					protocol.state = Menu(protocol)
				else: self.state = 'passwords_not_matching'
		elif self.state == 'passwords_not_matching':
			if keyID == '\r' or keyID == '\n':
				self.password = ''
				self.password_repeated = ''
				self.state = 'new_get_password'
		elif self.state == 'recurring_get_name':
			if str(keyID).isalnum(): self.name += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.name = self.name[0:-1]
			elif keyID == '\r' or keyID == '\n':
				self.state = 'recurring_get_password'
		elif self.state == 'recurring_get_password':
			if str(keyID).isalnum(): self.password += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.password = self.password[0:-1]
			elif keyID == '\r' or keyID == '\n':
				with protocol.factory.connection:
					player = protocol.factory.connection.execute('select * from player where name = ? and password = ?', (self.name, hashlib.sha256(self.password).hexdigest())).fetchone()
					if player:
						protocol.player = Player(*player)
						protocol.factory.connection.execute('insert into login (name, login) values (?, ?)', (protocol.player.name, datetime.datetime.now()))
						print protocol.player.name + ' logged in.'
						protocol.state = Menu(protocol)
					else: self.state = 'username_password_do_not_match'
		elif self.state == 'username_password_do_not_match':
			if keyID == '\r' or keyID == '\n':
				self.name = ''
				self.password = ''
				self.state = 'recurring_get_name'
		protocol.terminal.eraseDisplay()
		protocol.update_terminal()
	def render(self, protocol):
		if self.state == 'get_new_recurring': return 'Are you a recurring player? (y/n) ' + self.choice + '\n'
		elif self.state == 'new_get_name': return 'Welcome!\nPlease enter your name: ' + self.name + '\n'
		elif self.state == 'name_already_taken': return 'Sorry, this name is already taken. Please press return and try a different name.'
		elif self.state == 'new_get_password': return 'Please provide a password: ' + '*' * len(self.password) + '\n'
		elif self.state == 'repeat_password': return 'Please repeat the password: ' + '*' * len(self.password_repeated) + '\n'
		elif self.state == 'passwords_not_matching': return 'The passwords do not match. Please press return and try again.'
		elif self.state == 'recurring_get_name': return 'Welcome!\nPlease enter your name: ' + self.name + '\n'
		elif self.state == 'recurring_get_password': return 'Please enter your password: ' + '*' * len(self.password) + '\n'
		elif self.state == 'username_password_do_not_match': return 'Name and password do not match. Please press return and try again.'
class Menu(State):
	def __init__(self, protocol):
		self.choice = ''
		self.state = 'main_menu'
	def process_keystrokeReceived(self, keyID, modifier, protocol):
		if self.state == 'main_menu':
			if str(keyID).isalnum(): self.choice += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.choice = self.choice[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if self.choice == 'l':
					self.state = 'look'
				elif self.choice == 's':
					protocol.player.range = protocol.player.max_range
					protocol.player.speed = protocol.player.max_speed
					protocol.player.view = protocol.player.max_view
					protocol.player.hitpoints = protocol.player.max_hitpoints
					protocol.factory.add_protocol_to_queue(protocol)
					self.state = 'start_game'
				elif self.choice == 'r':
					self.state = 'help'
				elif self.choice == 'q':
					self.state = 'quit'
				self.choice = ''	
		elif self.state == 'look':
			if str(keyID).isalnum(): self.choice += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.choice = self.choice[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if self.choice == 'm':
					self.state = 'modify'
				elif self.choice == 'b':
					self.state = 'main_menu'
				self.choice = ''
		elif self.state == 'modify':
			if str(keyID).isalnum(): self.choice += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.choice = self.choice[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if protocol.player.range_updateable()[0] and self.choice == 'r':
					protocol.player.update_range(protocol)
					self.state = 'look'
				elif protocol.player.speed_updateable()[0] and self.choice == 's':
					protocol.player.update_speed(protocol)
					self.state = 'look'
				elif protocol.player.view_updateable()[0] and self.choice == 'v':
					protocol.player.update_view(protocol)
					self.state = 'look'
				elif protocol.player.hitpoints_updateable()[0] and self.choice == 'h':
					protocol.player.update_hitpoints(protocol)
					self.state = 'look'
				elif self.choice == 'l':
					self.state = 'look'
				self.choice = ''
		elif self.state == 'start_game':
			if keyID == 'b':
				protocol.factory.remove_protocol_from_queue_and_start_game_with_bots(protocol)
		elif self.state == 'help':
			if keyID == '\r' or keyID == '\n':
				self.state = 'main_menu'
		elif self.state == 'quit':
			if str(keyID).isalnum(): self.choice += keyID
			elif keyID == protocol.terminal.BACKSPACE: self.choice = self.choice[0:-1]
			elif keyID == '\r' or keyID == '\n':
				if self.choice == 'y':
					protocol.terminal.loseConnection()
				elif self.choice == 'n':
					self.state = 'main_menu'
				self.choice = ''
		protocol.terminal.eraseDisplay()
		protocol.update_terminal()
	def render(self, protocol):
		if self.state == 'main_menu': return 'Welcome ' + protocol.player.name.encode('ascii') + '!\n\nYou may ...\nLook at and modify your character (l)\nStart a game (s)\nRead the help section (r)\nQuit the game (q)\n\nYour choice: ' + self.choice + '\n'
		elif self.state == 'look': return 'Character: ' + protocol.player.name.encode('ascii') + '\n\nExperience: ' + str(int(protocol.player.experience))  + '\nLevel: ' + str(protocol.player.get_level()) + '\n\nRange: ' + str(protocol.player.max_range) + '\nSpeed: ' + str(protocol.player.max_speed) + '\nView: ' + str(protocol.player.max_view) + '\nHitpoints: ' + str(protocol.player.max_hitpoints) + '\n\nRange artefacts: ' + str(protocol.player.range_artefact) + '\nSpeed artefacts: ' + str(protocol.player.speed_artefact) + '\nView artefacts: ' + str(protocol.player.view_artefact) + '\nHitpoints artefacts: ' + str(protocol.player.hitpoints_artefact) + '\n\nYou may ...\nModify your character (m)\nBack to the main menu (b)\n\nYour choice: ' + self.choice + '\n'
		elif self.state == 'modify':
			if not protocol.player.max_range < 10 + Player.offset_range:
				range_text = 'You mastered your range ability!'
			elif not protocol.player.range_updateable()[1]:
				range_text = 'You do not have range artefacts left to improve your range.'
			else:
				if protocol.player.range_updateable()[2] < 0:
					range_text = 'You have enough range artefacts to improve your range but you need ' + str(-protocol.player.range_updateable()[2]) + ' more experience points.'
				else:
					range_text = 'You have enough range artefacts and experience to improve your range.'
			if not protocol.player.max_speed < 10 + Player.offset_speed:
				speed_text = 'You mastered your speed ability!'
			elif not protocol.player.speed_updateable()[1]:
				speed_text = 'You do not have speed artefacts left to improve your speed.'
			else:
				if protocol.player.speed_updateable()[2] < 0:
					speed_text = 'You have enough speed artefacts left to improve your speed but you need ' + str(-protocol.player.speed_updateable()[2]) + ' more experience points.'
				else:
					speed_text = 'You have enough speed artefacts and experience to improve your speed.'
			if not protocol.player.max_view < 10 + Player.offset_view:
				view_text = 'You mastered your view ability!'
			elif not protocol.player.view_updateable()[1]:
				view_text = 'You do not have view artefacts left to improve your view.'
			else:
				if protocol.player.view_updateable()[2] < 0:
					view_text = 'You have enough view artefacts left to improve your view but you need ' + str(-protocol.player.view_updateable()[2]) + ' more experience.'
				else:
					view_text = 'You have enough view artefacts and experience to improve your view.'
			if not protocol.player.max_hitpoints < 10 + Player.offset_hitpoints:
				hitpoints_text = 'You mastered your hitpoints ability!'
			elif not protocol.player.hitpoints_updateable()[1]:
				hitpoints_text = 'You do not have hitpoints artefacts left to improve your hitpoints.'
			else:
				if protocol.player.hitpoints_updateable()[2] < 0:
					hitpoints_text = 'You have enough hitpoints artefacts left to improve your hitpoints but you need ' + str(-protocol.player.hitpoints_updateable()[2]) + ' more experience.'
				else:
					hitpoints_text = 'You have enough hitpoints artefacts and experience to improve your hitpoints.'
			return 'You have ' + str(int(protocol.player.experience)) + ' experience points from which you have ' + str(int(protocol.player.experience_used())) + ' already used and therefore ' + str(int(protocol.player.experience - protocol.player.experience_used())) + ' left to spend.\nYou have ' + str(protocol.player.range_artefact) + ' range artefacts, ' + str(protocol.player.speed_artefact) + ' speed artefacts ' + str(protocol.player.view_artefact) + ' view artefacts, and ' + str(protocol.player.hitpoints_artefact) + ' hitpoints artefacts.\n' + range_text + '\n' + speed_text + '\n' + view_text + '\n' + hitpoints_text + '\n\nYou may ...\n'  + str(protocol.player.range_updateable()[0] and 'improve your range (r)\n' or '') + str(protocol.player.speed_updateable()[0] and 'improve your speed (s)\n' or '') + str(protocol.player.view_updateable()[0] and 'improve your view (v)\n' or '') + str(protocol.player.hitpoints_updateable()[0] and 'improve your hitpoints (h)\n' or '') + 'return to the character overview (l).\n\nYour choice: ' + self.choice + '\n'
		elif self.state == 'start_game': return 'Please wait until other players join ... ' + str(4 - len(protocol.factory.protocol_queues[protocol.player.get_level() - 1])) + ' to go.\n\nIf you would rather play with bots press "b" and start your game immediately.\n'
		elif self.state == 'help':
			return 'Go to http://roguebasin.roguelikedevelopment.org/index.php/Rogue_Mud for a detailed description of the game.\nPress return to get to the main menu.\n'
		elif self.state == 'quit':
			return 'Are you sure you want to quit? (y/n) ' + self.choice + '\n'
class Finish(State):
	def __init__(self, protocol):
		pass
	def process_keystrokeReceived(self, keyID, modifier, protocol):
		if keyID == '\r' or keyID == '\n':
			protocol.state = Menu(protocol)
		protocol.terminal.eraseDisplay()
		protocol.update_terminal()
	def render(self, protocol):
		if not protocol.player.hitpoints > 0:
			return 'You have lost this maze!\n\nPress return to go back to the main menu.'
		else:
			return 'You have won this game!\n\nPress return to go back to the main menu.'
class Game(State):
	def __init__(self, protocols):
		self.protocols = protocols
		self.protocols_lock = threading.Lock()
		average_level = int(sum([protocol.player.get_level() for protocol in self.protocols]) / len(self.protocols))
		self.rooms, self.walls = create_dungeon(0, 0, 32 * average_level + 2 * 4 * average_level, 32 * average_level + 2 * 4 * average_level, average_level)
		self.players, self.enemies, self.items, self.entry, self.exit = setup_dungeon(self.rooms, [protocol.player for protocol in self.protocols], average_level)
		self.players_lock = threading.Lock()
		self.enemies_lock = threading.Lock()
		self.items_lock = threading.Lock()
		self.map = create_map(self.walls + self.enemies + self.items + self.players + [self.entry] + [self.exit])
		self.map_lock = threading.RLock()
		path = []
		if len(self.players) - len(self.protocols):
			path = a_star((self.entry.x, self.entry.y), (self.exit.x, self.exit.y), [(tile.x, tile.y) for tile in self.walls], 2 ** 31 - 1)
			path.reverse()
		for i in range(len(self.players) - len(self.protocols) - 0): # Amounts of bots
			player = self.players[len(self.players) - 1 - i]
			break_off = 'not (self.individual.x, self.individual.y) == (self.game.exit.x, self.game.exit.y) and self.individual.hitpoints > 0'
			action_map = [('self.individual.target', 'self.charge()'), ('self.reach_item()', ()), ('self.target_enemy(random.random() < .5 and "individual" or "field")', ()), ('self.target_ally(random.random() < .5 and "individual" or "field")', ()), ('True', 'self.reach_exit()')]
			bot = PlayerBot(player, self, break_off, action_map, path)
			bot.daemon = True
			bot.start()
		for enemy in self.enemies:
			break_off = 'self.individual.hitpoints > 0'
			action_map = [('self.individual.hitpoints < self.individual.max_hitpoints * .5 and not self.flags[0]', 'self.reach_next_room()'), ('self.individual.hitpoints < self.individual.max_hitpoints * .25 and not self.flags[1]', 'self.reach_next_room()'), ('self.individual.target', 'self.charge()'), ('self.target_enemy(random.random() < .5 and "individual" or "field")', ()), ('self.target_ally(random.random() < .5 and "individual" or "field")', ()), ('True', 'self.walk_around()')]
			bot = EnemyBot(enemy, self, break_off, action_map)
			bot.daemon = True
			bot.start()
		self.accept_input = {}
		for protocol in self.protocols: self.accept_input[protocol] = False
		def trigger_updates():
			while self.protocols:
				current_time = time.time()
				for protocol in self.protocols:
					if protocol.player.target:
						if not (protocol.player.target in self.players + self.enemies and ((protocol.player.x - protocol.player.target.x) ** 2 + (protocol.player.y - protocol.player.target.y) ** 2) ** .5 <= protocol.player.range and (protocol.player.target.x, protocol.player.target.y) in self.calculate_line_of_sight(protocol.player.x, protocol.player.y, protocol.player.target.x, protocol.player.target.y)):
							protocol.player.target = None
							protocol.player.charge = 10
						elif protocol.player.charge > 0:
							protocol.player.charge -= protocol.player.speed
					if not protocol.player.hitpoints > 0:
						self.remove_protocol_from_game(protocol)
						protocol.state = Finish(protocol)
						protocol.terminal.eraseDisplay()
						protocol.update_terminal()
					twisted.internet.reactor.callFromThread(protocol.update_terminal)
					self.accept_input[protocol] = True
				time.sleep(max(.0, .5 - (time.time() - current_time)))
		trigger_updates_thread = threading.Thread(target=trigger_updates)
		trigger_updates_thread.daemon = True
		trigger_updates_thread.start()
	def process_keystrokeReceived(self, keyID, modifier, protocol):
		if self.accept_input[protocol]:
			if keyID == protocol.terminal.UP_ARROW or keyID == 'k': self._update_position(0, -1, protocol)
			elif keyID == protocol.terminal.DOWN_ARROW or keyID == 'j': self._update_position(0, 1, protocol)
			elif keyID == protocol.terminal.LEFT_ARROW or keyID == 'h': self._update_position(-1, 0, protocol)
			elif keyID == protocol.terminal.RIGHT_ARROW or keyID == 'l': self._update_position(1, 0, protocol)
			elif keyID == 'w': self._target_next_enemy(protocol)
			elif keyID == 's': self._target_previous_enemy(protocol)
			elif keyID == 'e': self._target_next_ally(protocol)
			elif keyID == 'd': self._target_previous_ally(protocol)
			elif keyID == 'q' and protocol.player.target and protocol.player.target in self.players + self.enemies and not protocol.player.charge > 0: self._trigger_individual_action(protocol)
			elif keyID == 'a' and protocol.player.target and protocol.player.target in self.players + self.enemies and not protocol.player.charge > 0: self._trigger_field_action(protocol)
			else: return
			self.accept_input[protocol] = False
	def render(self, protocol):
		blank = twisted.conch.insults.text.flatten(twisted.conch.insults.text.attributes.bg.black[twisted.conch.insults.text.attributes.fg.white[' ']], twisted.conch.insults.helper.CharacterAttribute())
		field_of_view = self.calculate_field_of_view(protocol)
		hud = ['!' * min(10 - protocol.player.charge, 10), 'HP: ' + str(int(protocol.player.hitpoints)) + ' View: ' + str(int(protocol.player.view)) + ' Range: ' + str(int(protocol.player.range)) + ' Speed: ' + str(int(protocol.player.speed)) + ' Experience: ' + str(int(protocol.player.experience))]
		skip = 0
		for j in range(protocol.player.y - protocol.factory.height / 2, protocol.player.y - protocol.factory.height / 2 + protocol.factory.height):
			for i in range(protocol.player.x - protocol.factory.width / 2, protocol.player.x - protocol.factory.width / 2 + protocol.factory.width):
				try:
					if skip: skip -= 1
					elif j - protocol.player.y + protocol.factory.height / 2 == 1 and i - protocol.player.x + protocol.factory.width / 2 == 1 and hud[0]:
						skip = len(hud[0]) - 1
						yield hud[0]
					elif j - protocol.player.y + protocol.factory.height / 2 == 2 and i - protocol.player.x + protocol.factory.width / 2 == 1 and hud[1]:
						skip = len(hud[1]) - 1
						yield hud[1]
					elif i < 0 or j < 0: yield blank
					elif (i, j) in field_of_view:
						if not self.map[i][j]: yield '.'
						else: yield self.map[i][j][-1] == protocol.player.target and '*' or self.map[i][j][-1].character
					elif isinstance(self.map[i][j][-1], Wall) or isinstance(self.map[i][j][-1], Player): yield self.map[i][j][-1].character
					else: yield blank
				except: yield blank
			yield '\n'
	def remove_protocol_from_game(self, protocol):
		with self.map_lock:
			self.map[protocol.player.x][protocol.player.y].pop(self.map[protocol.player.x][protocol.player.y].index(protocol.player))
			with self.protocols_lock: self.protocols.pop(self.protocols.index(protocol))
			with self.players_lock: self.players.pop(self.players.index(protocol.player))
			with self.players_lock:
				for player in self.players:
					if player.target == protocol.player:
						player.target = None
			with self.enemies_lock:
				for enemy in self.enemies:
					if enemy.target == protocol.player:
						enemy.target = None
	def _update_position(self, dx, dy, protocol):
		with self.map_lock: 
			if not [tile for tile in self.map[protocol.player.x + dx][protocol.player.y + dy] if isinstance(tile, Wall) or isinstance(tile, Player) or isinstance(tile, Enemy)]:
				update_map(self.map, protocol.player, dx, dy)
				protocol.player.x += dx
				protocol.player.y += dy
				protocol.player.evaluate_effect(self)
		if [tile for tile in self.map[protocol.player.x][protocol.player.y] if isinstance(tile, Exit)] or not protocol.player.hitpoints > 0:
			self.remove_protocol_from_game(protocol)
			with protocol.factory.connection:
				protocol.factory.connection.execute('update player set experience = ?, range_artefact = ?, speed_artefact = ?, view_artefact = ?, hitpoints_artefact = ? where name = ?', (protocol.player.experience, protocol.player.range_artefact, protocol.player.speed_artefact, protocol.player.view_artefact, protocol.player.hitpoints_artefact, protocol.player.name))
			protocol.state = Finish(protocol)
			protocol.terminal.eraseDisplay()
			protocol.update_terminal()
	def _target_next_enemy(self, protocol):
		with self.enemies_lock:
			enemies = [(enemy, distance) for enemy, distance in [(enemy, ((protocol.player.x - enemy.x) ** 2 + (protocol.player.y - enemy.y) ** 2) ** .5) for enemy in self.enemies] if not distance > protocol.player.view and not distance > protocol.player.range and (enemy.x, enemy.y) in self.calculate_line_of_sight(protocol.player.x, protocol.player.y, enemy.x, enemy.y)]
			enemies = [enemy for enemy, distance in sorted(enemies, key=lambda enemy_distance: enemy_distance[1])]
			if protocol.player.target in enemies and enemies:
				protocol.player.target = enemies[(enemies.index(protocol.player.target) + 1) % len(enemies)]
				protocol.player.charge = 10
			elif enemies:
				protocol.player.charge = 10
				protocol.player.target = enemies[0]
	def _target_previous_enemy(self, protocol):
		with self.enemies_lock:
			enemies = [(enemy, distance) for enemy, distance in [(enemy, ((protocol.player.x - enemy.x) ** 2 + (protocol.player.y - enemy.y) ** 2) ** .5) for enemy in self.enemies] if not distance > protocol.player.view and not distance > protocol.player.range and (enemy.x, enemy.y) in self.calculate_line_of_sight(protocol.player.x, protocol.player.y, enemy.x, enemy.y)]
			enemies = [enemy for enemy, distance in sorted(enemies, key=lambda enemy_distance: enemy_distance[1])]
			if protocol.player.target in enemies and enemies:
				protocol.player.target = enemies[(enemies.index(protocol.player.target) - 1) % len(enemies)]
				protocol.player.charge = 10
			elif enemies:
				protocol.player.target = enemies[-1]
				protocol.player.charge = 10
	def _target_next_ally(self, protocol):
		with self.players_lock:
			players = [(player, distance) for player, distance in [(player, ((protocol.player.x - player.x) ** 2 + (protocol.player.y - player.y) ** 2) ** .5) for player in self.players if not player == protocol.player] if not distance > protocol.player.view and not distance > protocol.player.range and (player.x, player.y) in self.calculate_line_of_sight(protocol.player.x, protocol.player.y, player.x, player.y) and not player == protocol.player]
			players = [player for player, distance in sorted(players, key=lambda player_distance: player_distance[1])]
			if protocol.player.target in players and players:
				protocol.player.target = players[(players.index(protocol.player.target) + 1) % len(players)]
				protocol.player.charge = 10
			elif players:
				protocol.player.target = players[0]
				protocol.player.charge = 10
	def _target_previous_ally(self, protocol):
		with self.players_lock:
			players = [(player, distance) for player, distance in [(player, ((protocol.player.x - player.x) ** 2 + (protocol.player.y - player.y) ** 2) ** .5) for player in self.players if not player == protocol.player] if not distance > protocol.player.view and not distance > protocol.player.range and (player.x, player.y) in self.calculate_line_of_sight(protocol.player.x, protocol.player.y, player.x, player.y) and not player == protocol.player]
			players = [player for player, distance in sorted(players, key=lambda player_distance: player_distance[1])]
			if protocol.player.target in players and players:
				protocol.player.target = players[(players.index(protocol.player.target) - 1) % len(players)]
				protocol.player.charge = 10
			elif players:
				protocol.player.target = players[-1]
				protocol.player.charge = 10
	def _trigger_individual_action(self, protocol):
		protocol.player.action = 'individual'
		protocol.player.experience += protocol.player.evaluate_action(self)
	def _trigger_field_action(self, protocol):
		protocol.player.action = 'field'
		protocol.player.experience += protocol.player.evaluate_action(self)
	def _calculate_line_of_sight(self, x0, y0, dx, dy, octant, fields, circular=False):
		upper_view_intercept = 1.0
		upper_view_slope = -1.0
		lower_view_intercept = 0.0
		lower_view_slope = 2.0
		boundary_slope = float(dy) / float(dx)
		for x, y in [coordinate for coordinate in line(0, 0, dx, dy)][1:]:
			if circular and x > dx * math.cos((math.pi / 4.0) * boundary_slope): break
			y_up = boundary_slope * x + 1
			y_low = boundary_slope * x + 0 # (x, int(y_low)) corresponds to game-grid
			last_lower = 1
			last_upper = 1
			tiles = {0: lambda x, y: self.map[x + x0][y + y0], 1: lambda x, y: self.map[-x + x0][y + y0], 2: lambda x, y: self.map[x + x0][-y + y0], 3: lambda x, y: self.map[-x + x0][-y + y0], 4: lambda x, y: self.map[y + x0][x + y0], 5: lambda x, y: self.map[-y + x0][x + y0], 6: lambda x, y: self.map[y + x0][-x + y0], 7: lambda x, y: self.map[-y + x0][-x + y0]}[octant]
			try: 
				if [tile for tile in tiles(x, int(y_up)) if isinstance(tile, Wall) or isinstance(tile, Individual)]:
					if lower_view_slope * x + lower_view_intercept > int(y_up): lower_view_slope = (int(y_up) - lower_view_intercept) / (x - 0)
					for x_ in range(last_lower, x):
						if [tile for tile in tiles(x_, int(boundary_slope * x_ + 0)) if isinstance(tile, Wall) or isinstance(tile, Individual)]:
							if lower_view_slope * x_ + lower_view_intercept < int(boundary_slope * x_ + 1):
								lower_view_slope = (int(y_up) - (boundary_slope * x_ + 1)) / (x - x_)
								lower_view_intercept = int(y_up) - lower_view_slope * x
								last_lower = x_
				if [tile for tile in tiles(x, int(y_low)) if isinstance(tile, Wall) or isinstance(tile, Individual)]:
					if upper_view_slope * x + upper_view_intercept < int(y_low) + 1: upper_view_slope = (int(y_low) + 1 - upper_view_intercept) / (x - 0)
					for x_ in range(last_upper, x):
						if [tile for tile in tiles(x_, int(boundary_slope * x_ + 1)) if isinstance(tile, Wall) or isinstance(tile, Individual)]:
							if upper_view_slope * x_ + upper_view_intercept > int(boundary_slope * x_ + 1):
								upper_view_slope = (int(y_low) + 1 - (boundary_slope * x_ + 1)) / (x - x_)
								upper_view_intercept = int(y_low) + 1 - upper_view_slope * x
								last_upper = x_
			except: return fields
			if upper_view_intercept < 0.0 or upper_view_intercept > 1.0 or lower_view_intercept < 0.0 or lower_view_intercept > 1.0: return fields
			field = {0: lambda: (x + x0, y + y0), 1: lambda: (-x + x0, y + y0), 2: lambda: (x + x0, -y + y0), 3: lambda: (-x + x0, -y + y0), 4: lambda: (y + x0, x + y0), 5: lambda: (-y + x0, x + y0), 6: lambda: (y + x0, -x + y0), 7: lambda: (-y + x0, -x + y0)}[octant]
			fields.extend([field()])
			if not (lower_view_slope * x + lower_view_intercept > y and upper_view_slope * x + upper_view_intercept < y + 1): return fields
		return fields
	def calculate_line_of_sight(self, x0, y0, x1, y1):
		if x0 <= x1 and y0 <= y1 and abs(x1 - x0) > abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, x1 - x0, y1 - y0, 0, [])
		elif x0 > x1 and y0 <= y1 and abs(x1 - x0) > abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, x0 - x1, y1 - y0, 1, [])
		elif x0 <= x1 and y0 > y1 and abs(x1 - x0) > abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, x1 - x0, y0 - y1, 2, [])
		elif x0 > x1 and y0 > y1 and abs(x1 - x0) > abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, x0 - x1, y0 - y1, 3, [])
		elif x0 <= x1 and y0 <= y1 and abs(x1 - x0) <= abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, y1 - y0, x1 - x0, 4, [])
		elif x0 > x1 and y0 <= y1 and abs(x1 - x0) <= abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, y1 - y0, x0 - x1, 5, [])
		elif x0 <= x1 and y0 > y1 and abs(x1 - x0) <= abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, y0 - y1, x1 - x0, 6, [])
		elif x0 > x1 and y0 > y1 and abs(x1 - x0) <= abs(y1 - y0):
			return self._calculate_line_of_sight(x0, y0, y0 - y1, x0 - x1, 7, [])
	def calculate_field_of_view(self, protocol):
		def calculate_octant(octant, protocol, fields):
			for dy in range(protocol.player.view + 1):
				self._calculate_line_of_sight(protocol.player.x, protocol.player.y, protocol.player.view, dy, octant, fields, True)
		fields = []
		threads = [threading.Thread(target=calculate_octant, args=(octant, protocol, fields)) for octant in range(8)]
		for thread in threads: thread.start()
		for thread in threads: thread.join()
		return fields

class RogueMud(twisted.conch.insults.insults.TerminalProtocol):
	def __init__(self):
		self.player = None
	def connectionMade(self):
		self.terminal.resetModes([twisted.conch.insults.insults.modes.IRM])
		self.terminal.resetPrivateModes([twisted.conch.insults.insults.privateModes.CURSOR_MODE])
		self.state = Login(self)
		self.terminal.eraseDisplay()
		self.update_terminal()
	def connectionLost(self, reason):
		if isinstance(self.state, Menu):
			self.factory.remove_protocol_from_queue(self)
		elif isinstance(self.state, Game):
			self.state.remove_protocol_from_game(self)
		if self.player:
			with self.factory.connection:
				self.factory.connection.execute('insert into logout (name, logout) values (?, ?)', (self.player.name, datetime.datetime.now()))
				print self.player.name + ' logged out.'
	def keystrokeReceived(self, keyID, modifier):
		self.state.process_keystrokeReceived(keyID, modifier, self)
	def update_terminal(self):
		self.terminal.cursorPosition(0, 0)
		self.terminal.write(''.join([c for c in self.state.render(self)][:-1]))

class RogueMudFactory(twisted.internet.protocol.ServerFactory):
	def __init__(self, width, height):
		self.width = width
		self.height = height
		self.protocol_queues = [[] for i in range(10)]
		self.connection = sqlite3.connect('/home/roguemud/rogue_mud.db')
		#self.connection = sqlite3.connect('./rogue_mud.db')
		with self.connection:
			if not self.connection.execute('select * from sqlite_master where type = ?', ('table', )).fetchone():
				self.connection.execute('create table player (name text, password text, experience integer, range_artefact integer, speed_artefact integer, view_artefact integer, hitpoints_artefact integer, range integer, speed integer, view integer, hitpoints integer)')
				self.connection.execute('create table login (name text, login timestamp)')
				self.connection.execute('create table logout (name text, logout timestamp)')
	def buildProtocol(self, addr):
		protocol = twisted.conch.telnet.TelnetTransport(twisted.conch.telnet.TelnetBootstrapProtocol, twisted.conch.insults.insults.ServerProtocol, RogueMud)
		protocol.factory = self
		return protocol
	def add_protocol_to_queue(self, protocol):
		self.protocol_queues[protocol.player.get_level() - 1].extend([protocol])
		for protocol in self.protocol_queues[protocol.player.get_level() - 1]: protocol.update_terminal()
		if len(self.protocol_queues[protocol.player.get_level() - 1]) < 4: return
		game = Game(self.protocol_queues[protocol.player.get_level() - 1])
		for protocol in self.protocol_queues[protocol.player.get_level() - 1]: protocol.state = game
		self.protocol_queues[protocol.player.get_level() - 1] = []
	def remove_protocol_from_queue(self, protocol):
		if protocol in self.protocol_queues[protocol.player.get_level() - 1]:
			self.protocol_queues[protocol.player.get_level() - 1].pop(self.protocol_queues[protocol.player.get_level() - 1].index(protocol))
			for protocol in self.protocol_queues[protocol.player.get_level() - 1]: protocol.update_terminal()
	def remove_protocol_from_queue_and_start_game_with_bots(self, protocol):
		self.protocol_queues[protocol.player.get_level() - 1].pop(self.protocol_queues[protocol.player.get_level() - 1].index(protocol))
		game = Game([protocol])
		protocol.state = game
		for protocol in self.protocol_queues[protocol.player.get_level() - 1]: protocol.update_terminal()

application = twisted.application.service.Application("rogue_mud")
service = twisted.application.internet.TCPServer(6023, RogueMudFactory(80, 24))
service.setServiceParent(application)