JUEGO PARA APRENDER ESTRUCTURAS DE DATOS Y
ALGORITMOS
GAME FOR LEARNING DATA STRUCTURES AND ALGORITHMS
Alejand o Jim´enez S´anchez
DOBLE GRADO EN INGENIER´
IA INFORM´
ATICA Y MATEM´
ATICAS
FACULTAD DE INFORM´
ATICA
UNIVERSIDAD COMPLUTENSE DE MADRID
T abajo Fin de G ado en Ingenie ´ıa In o m´a ica
Cu so 2020/2021
Feb e o de 2021
Di ec o :
I ´an Ga c´ıa-Maga i˜no Ga c´ıa
´
Indice gene al
1. In oducci´on 4
1.1. In oduc ion..................................... 4
1.2. In oducci´on a los juegos se ios. Concep os p incipales . . . . . . . . . . . . . . 5
1.3. In oducci´on a la aplicaci´on desa ollada . . . . . . . . . . . . . . . . . . . . . 7
1.4. T abajo exis en e y aplicaciones simila es . . . . . . . . . . . . . . . . . . . . . 11
1.5. Plande abajo................................... 13
2. Algo i mos e In e acci´on 15
2.1. In oducci´on..................................... 15
2.2. O denaci´on po inse ci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1. Tu o ialdeljuego.............................. 16
2.2.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 18
2.2.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 21
2.3. O denaci´on po selecci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1. Tu o ialdeljuego.............................. 24
2.3.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 25
2.3.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 26
2.4. O denaci´on po el m´e odo de la bu buja . . . . . . . . . . . . . . . . . . . . . 27
2.4.1. Tu o ialdeljuego.............................. 28
2.4.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 29
2.4.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 30
2.5. O denaci´on po mezclas (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1. Tu o ialdeljuego.............................. 33
2.5.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 35
2.5.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 36
2.6. T´ecnica de en ana deslizan e . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6.1. In oducci´on a la ´ecnica . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6.2. Tu o ialdeljuego.............................. 40
2.6.3. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 42
2.6.4. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 44
3. Dise˜no y aspec os de la aplicaci´on 45
3.1. Clases y p ocesos p incipales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1. Clases .................................... 45
3.1.2. Diag amas de secuencia de dos p ocesos p incipales . . . . . . . . . . . 48
3.2. Feedback p opo cionado y o as uncionalidades . . . . . . . . . . . . . . . . . 50
3.2.1. Feedback................................... 50
3.2.2. Log con la in e acci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1
4. E aluaci´on con Usua ios 54
4.1. P ime as p uebas con usua ios . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.1. In oducci´on................................. 54
4.1.2. P uebas ealizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.3. Resul ados y posibles mejo as . . . . . . . . . . . . . . . . . . . . . . . 55
4.2. Teo ´ıa sob e p uebas de usabilidad . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3. P uebas inales con usua ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4. Resul ados de las p uebas y conclusiones . . . . . . . . . . . . . . . . . . . . . 59
4.4.1. Cues iona io p e io . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4.2. Cues iona io inal.............................. 61
4.4.3. An´alisis de los logs ............................. 62
5. Conclusiones y abajo u u o 65
5.1. Conclusiones..................................... 65
5.2. T abajo u u o ................................... 65
5.3. Conclusions ..................................... 66
5.4. Fu u ewo k..................................... 66
Bibliog a ´ıa 67
2
Resumen
Las asigna u as de algo i mos y es uc u as de da os son una pa e undamen al en los
es udios de in o m´a ica. En una p ime a ap oximaci´on a ellas, el alumno puede ene di-
icul ades en su comp ensi´on. Es po ello que puede se buena idea disminui el ni el de
abs acci´on, elegi un caso conc e o y mos a la aplicaci´on del algo i mo a dicho ejemplo.
Adem´as, nume osos es udios es ´an a a o de que sea ambi´en el es udian e el que ap ende
po s´ı mismo median e la in e acci´on con un juego elacionado con el concep o a es udia .
Es po ello que se implemen a una aplicaci´on en Uni y que mues a las ideas p incipales
de algunos de los algo i mos b´asicos y es uc u as de da os ´ıpicas, y que no se limi a a
mos a su uncionamien o, sino que pe mi e la in e acci´on del usua io, gua dando ambi´en
es ad´ıs icas sob e su endimien o. En es a memo ia se explican inicialmen e los obje i os y
las aplicaciones simila es exis en es. En los cap´ı ulos siguien es, se desc ibe el desa ollo de la
aplicaci´on. P ime o, se cen a en cada juego implemen ado y la in e acci´on pedida al usua io
en cada caso; despu´es, en los aspec os del dise˜no y desa ollo de la aplicaci´on. La memo ia
inaliza con los esul ados de las p uebas con usua ios.
Palab as cla e
Algo i mos, ap endizaje basado en juegos, es uc u as de da os, p uebas de usabilidad,
Uni y.
Abs ac
Algo i hms and da a s uc u es a e co e subjec s in compu e science cou ses. In a i s
app oach, he s uden may ind hem di icul . In consequence, i could be a good idea o use
a lowe le el o abs ac ion, choose a conc e e example and show he low o he algo i hm
applied o ha case. In addi ion, he e a e a lo o a icles ha uphold he bene i s o he
s uden s i hey in e ac wi h a game abou hese concep s. The e o e, a Uni y game has been
de eloped in o de o show he main concep s o hese mos common algo i hms and da a
s uc u es. I allows use s o in e ac wi h i o make lea ning mo e a ac i e, and sa es da a
abou hei pe o mance. In his wo k, ini ially, he aims o he applica ion a e explained,
and simila games a e analyzed. Then, he e a e wo chap e s abou he de elopmen o
he applica ion. The i s one is ocused on he games ha a e implemen ed and he use
in e ac ion. The second one explains he design and he de elopmen o he game. Finally,
he ou comes o he usabili y es s a e shown.
Keywo ds
Algo i hms, game-based lea ning, da a s uc u es, usabili y es ing, Uni y.
3
Cap´ı ulo 1
In oducci´on
Las asigna u as de algo i mos y es uc u as de da os son b´asicas en los cu sos de ciencias
de la compu aci´on. Adem´as, son muchos los au o es que de ienden que inco po a ideojuegos
en el p oceso educa i o es una buena idea. Es o ha se ido de mo i aci´on pa a desa olla
una aplicaci´on educa i a en Uni y sob e ciencias de la compu aci´on.
En es e abajo se explica dicho juego educa i o sob e algo i mos y es uc u as de da-
os. El obje i o es que el usua io pueda simula el lujo de un algo i mo haciendo acciones
simila es a las que ha ´ıa el o denado sob e su memo ia, ap endiendo as´ı c´omo unciona el
algo i mo. Adem´as, la aplicaci´on gua da es ad´ıs icas sob e el endimien o de los jugado es y
iene ca ac e ´ıs icas ´ıpicas de los juegos como pun uaciones.
En es e cap´ı ulo in oduc o io se exponen concep os b´asicos sob e juegos se ios, se analizan
las aplicaciones simila es y se expone el plan de abajo as una e apa de in es igaci´on. El
segundo cap´ı ulo se cen a en los algo i mos implemen ados en el juego y la in e acci´on
eque ida al usua io. El e ce o explica el dise˜no global as´ı como uncionalidades adicionales.
Se adjun an ambi´en algunos diag amas UML. Po ´ul imo, el cua o cap´ı ulo explica los
esul ados de las p uebas de usabilidad ealizadas al inaliza el desa ollo.
1.1. In oduc ion
Algo i hms and da a s uc u es a e co e subjec s in compu e science cou ses. In addi ion,
a lo o esea che s uphold ha inco po a ing ideogames in educa ion is a good idea. This
has been a mo i a ion o de elop a Uni y educa ional applica ion abou compu e science.
In his wo k, his educa ional game abou algo i hms and da a s uc u es is explained.
The aim is ha he use can simula e he low o an algo i hm by execu ing ac ions ha a e
simila o hose execu ed by he compu e on i s memo y. Thus, he s uden would lea n how
he algo i hm wo ks. In addi ion, he applica ion sa es s a is ics abou he pe o mance o
he playe s and includes some game ea u es like sco es.
In his in oduc o y chap e , basic concep s abou se ious games a e explained a e some
esea ch. The second chap e ocuses on hese algo i hms implemen ed in he game and
he in e ac ion ha is equi ed o playe s. The hi d one is abou he o e all design o he
applica ion and addi ional unc ionali ies. Some UML diag ams a e shown in his chap e
oo. Finally, he ou comes o he usabili y es s ha we e pe o med a e he de elopmen
was inished a e explained in he ou h chap e .
4

1.2. In oducci´on a los juegos se ios. Concep os p inci-
pales
Dado que el obje i o de es e abajo es desa olla un juego se io educa i o sob e ciencias
de la compu aci´on, en p ime luga se exponen concep os sob e es e campo. Es a in es iga-
ci´on ha ayudado al dise˜no y desa ollo de la aplicaci´on, p opo cionando ideas ya p obadas
po o os au o es. Es a secci´on in oduc o ia se basa p incipalmen e en la e e encia [1].
Se sabe que los juegos han es ado p esen es en las di e en es sociedades desde hace mucho
iempo. Con la apa ici´on de o denado es, consolas y o os ma e iales in o m´a icos se ab ie on
nue as posibilidades y se comenza on a desa olla los llamados juegos digi ales. Es e campo
de los ideojuegos se ha desa ollado eno memen e en los ´ul imos a˜nos, y una de las cla es
de es e c ecimien o es el hecho de p o oca en sus usua ios una eno me a acci´on. Como se
de ini´o en [2], el jugado puede llega al llamado es ado men al de lujo, donde queda o al-
men e concen ado e inme so en el juego. O o concep o elacionado es el de lujo del juego
[3], ca ac e izado po concen aci´on exclusi a, sen imien o de con ol sob e el juego, ene
eedback inmedia o de las acciones ealizadas y a on a me as cla as. Po an o, consegui
ese es ado se ´a uno de los obje i os del equipo de desa ollo de un juego digi al.
Es as ca ac e ´ıs icas de los juegos se pueden ap o echa pa a p op´osi os que aba can
no solo el en e enimien o, sino ambi´en o os campos. En [1] se comen a el ejemplo de la
ele isi´on. Pasado un iempo as su apa ici´on, se empeza on a desa olla p og amas con
p op´osi os educa i os, po ci a un campo dis in o al en e enimien o. De hecho, algunos jue-
gos de mesa ya en´ıan p op´osi os adicionales a di e i se. Po ´ul imo, es cla o que los juegos
depo i os ienen la en aja adicional de mejo a la salud.
Se de ine juego se io como aquel juego digi al que pe sigue en e ene y consegui al menos
un obje i o m´as. No obs an e, no hay un consenso o al en es a de inici´on, ya que algunos
au o es se cen an en la in enci´on del desa ollado del juego, mien as que o os se cen an
en la in enci´on del usua io. En cambio, s´ı es com´un la idea de ene al menos un obje i o
adem´as del en e enimien o. Es as me as adicionales se denominan obje i os ca ac e ´ıs icos.
Los juegos se ios pueden se de cualquie g´ene o, ya que se puede busca la consecuci´on de
los obje i os ca ac e ´ıs icos po medio de di e sas em´a icas. Si un juego se io iene ´exi o,
el jugado se ´a dis in o despu´es de habe jugado espec o a an es: end ´a m´as conocimien o,
mejo salud o sus opiniones hab ´an cambiado. El ´e mino “juego se io” gan´o popula idad en
2002 con el a ´ıculo de Sawye y Reje ski [4] y con el juego Ame ica’s A my [5].
Relacionado con los concep os de lujo explicados m´as a iba, Sinclai [6] in oduce el
lujo dual pa a juegos se ios: hay que busca an o el a ac i o del juego (buena expe ien-
cia de usua io) como su e ec i idad (consecuci´on del obje i o ca ac e ´ıs ico). El a ac i o
se consigue con un equilib io en e la di icul ad y el ni el de habilidad del usua io. Como
es e ´ul imo es din´amico (es espe able que la habilidad mejo e con la p ´ac ica del juego),
hab ´ıa que adap a la di icul ad din´amicamen e ambi´en pa a que el jugado no caiga en el
edio. El o o ex emo (la di icul ad supe a ampliamen e a las habilidades) se ca ac e iza po
us aci´on po pa e del usua io. En cuan o a la e ec i idad, en es e a ´ıculo [6] se p esen a
un juego se io elacionado con el depo e (uno de los llamados exe games). Po an o, la
e ec i idad consis i ´ıa en encon a un equilib io en e la capacidad ´ısica del usua io y la
in ensidad del eje cicio, man eni´endose siemp e la exigencia del juego en un in e alo que no
esul e i ial pa a el usua io (no gene a ´ıa bene icio en la salud del mismo) pe o que ampoco
5
exija demasiado (pod ´ıan ocu i lesiones). Es o se ex iende a muchos o os g´ene os de juegos.
Habi ualmen e se elacionan los concep os de juegos educa i os, “edu ainmen ” ([7], don-
de se jun an educa ion yen e ainmen ) y ap endizaje basado en juegos (game-based lea ning,
[7]) con el concep o de juegos se ios, ya que se es ablece la iden i icaci´on del obje i o ca ac-
e ´ıs ico con el ap endizaje. Es o no es cie o, ya que el obje i o ca ac e ´ıs ico puede se
muy di e so (pone se en o ma, desa olla habilidades sociales o de esoluci´on de p oblemas,
p omo e cie os alo es). Po an o, los juegos educa i os y es o de concep os elacionados
se iden i ican m´as bien como un subconjun o es ic o de los juegos se ios.
Pese a que la indus ia de los juegos se ios ha c ecido ecien emen e, es ´a muy lejos de lle-
ga al campo de los ideojuegos de en e enimien o (nomencla u a usada pa a aquellos cuyo
obje i o es solo en e ene ). Una az´on de es o es que el p´ublico obje i o suele se mucho m´as
educido y espec´ı ico que en el caso de ideojuegos de en e enimien o. O o incon enien e es
que los p esupues os pa a el desa ollo de la aplicaci´on suelen se meno es. Adem´as, es m´as
complejo su desa ollo, ya que habi ualmen e hay que inclui en el p oceso a expe os del
dominio del obje i o ca ac e ´ıs ico. Es a mul idisciplina idad puede complica el desa ollo
de la aplicaci´on, al con i i pe sonas con di e en es o mas de esol e p oblemas y de pensa ,
o incluso las disciplinas pueden ene e minolog´ıa dis in a. Po ´ul imo, como es un campo
menos amplio, los desa ollado es de juegos se ios ienen menos e e encias en las que basa se.
Como ya se ha comen ado, es buena idea (y no solo en juegos se ios, sino en cualquie
ipo de juego) adap a se a la habilidad del usua io. Adem´as, el hecho de que cada juego se io
enga unos usua ios obje i o muy espec´ı icos, hace a´un m´as necesa io si cabe la adap aci´on
de la di icul ad a las habilidades.
Dado que una de las p incipales amas de los juegos se ios son los juegos educa i os y en
es a memo ia se explica el dise˜no y desa ollo de una aplicaci´on cuyo obje i o ca ac e ´ıs i-
co es el ap endizaje, es in e esan e cen a se ambi´en en algunos aspec os educa i os. En el
a ´ıculo mencionado an e io men e [7], M. P ensky asegu a que la mo i aci´on que despie an
los juegos en los ni˜nos se debe al ap endizaje que p opo cionan (y es a mo i aci´on es deseable
al en en a se a un ap endizaje). Los ideojuegos ense˜nan, en un ni el subyacen e, a ecopila
in o maci´on y oma decisiones ´apidamen e, desa olla es a egias pa a supe a p oblemas
o a coope a con o os jugado es.
En cuan o a las di e en es o mas de ap ende , el modelo de e e encia e´o ico 8LEM (Eigh
Lea ning E en s Model) [8] desc ibe el ap endizaje a pa i de ocho e en os de ap endizaje
b´asicos, siendo un e en o de ap endizaje la desc ipci´on de la ac i idad de un alumno y un
maes o en un con ex o educa i o. Los ocho e en os b´asicos son los siguien es:
Imi aci´on: Obse a y, pos e io men e, imi a . El p o eso si e como modelo, pe o es e
modelo no iene po qu´e se suyo.
Recepci´on: Recibi in o maci´on emi ida po el p o eso in encionadamen e pa a ense˜na .
Eje cicio: En campos en los que hay que au oma iza habilidades, se ap ende p ac i-
cando. El u o debe guia y p opo ciona eedback adecuado.
Explo aci´on: Ap ende median e p opia in es igaci´on con cie a libe ad, buscando en-
e da os. El p o eso p opo ciona ´ıa uen es de in o maci´on adecuadas.
6
Expe imen aci´on: P ueba y e o , es deci , manipula el en o no y obse a consecuen-
cias. El alumno p oba ´ıa as´ı odas las combinaciones posibles o aquellas que conside e
in e esan es.
C eaci´on: C ea nue o con enido, donde el ´e mino “nue o” se e ie e al alumno, no
necesa iamen e con enido que no es ´e ya c eado po ninguna o a pe sona.
Au o e lexi´on: Re lexiona sob e los p opios p ocesos cogni i os.
Deba e: Ap ende median e in e acciones sociales, como deba es en los que se de iende
una posici´on an e un con lic o, y es ´an p omo idos y mode ados po un u o . La
in e acci´on puede se as´ınc ona (como en un o o) o s´ınc ona.
Como ya se ha dicho, el desa ollo de juegos se ios es mul idisciplina . Po an o, si se quie-
e desa olla un so wa e educa i o (po ejemplo), con iene conoce alguna de es as eo ´ıas
pa a pode aplica los p incipios al desa ollo. Tambi´en ela i o a es e campo, el a ´ıculo
[9] y o os esul ados an´alogos p oponen m´as cla es pa a un juego educa i o de ´exi o: p o-
po ciona eedback inmedia o, ene g an ni el de in e acci´on, desa ´ıo y compe i i idad; y
consegui que el usua io enga mo i aci´on in ´ınseca pa a juga . Como se indica en [1], un
juego se io ambi´en puede se u ilizado a pa i de mo i aci´on ex ´ınseca (usa la aplicaci´on
como he amien a pa a consegui cie a me a). Po ejemplo, un es udian e que quie e supe a
una p ueba: u iliza la aplicaci´on pa a es udia y ap oba el examen, y despu´es ya no iene la
necesidad de usa la.
En el dise˜no de ideojuegos y juegos se ios in e ienen muchos o os ac o es. Adem´as de
los ob ios (como pod ´ıa se de ini el p´ublico obje i o) hay o os como pensa en el pe il de
los posibles jugado es (Ba le [10] public´o un modelo pa a juegos MUDs basado en kille s,
achie e s,socialize s yexplo e s) y la adap aci´on del juego a cada ipo. Tambi´en hay que
conside a aspec os como la necesidad de supe isi´on po pa e de un ins uc o , el en o no
donde se debe juga , la posibilidad de ol e a juga (algunos juegos es ´an dise˜nados pa a
juga una sola ez; o os, pa a juga a ias eces) o el iempo necesa io pa a juga (el iempo
necesa io pa a cada pa ida es un aspec o impo an e).
Las ideas y a ´ıculos sob e juegos se ios son en la ac ualidad muy nume osos. La aplicaci´on
que se explica en es a memo ia ha seguido algunos de los concep os expues os en es a secci´on
in oduc o ia, con mecanismos muy simples pe o que (se p e ende) mejo an la expe iencia
de usua io espec o a las p ime as e siones que se implemen a on, donde no se u ie on en
cuen a es os concep os.
1.3. In oducci´on a la aplicaci´on desa ollada
Hay di e en es a ´ıculos sob e el p oceso de es udio de cu sos elacionados con las ciencias
de la compu aci´on. Po ejemplo, en [11] se p esen an los esul ados de una encues a en la
que pa icipa on m´as de 500 es udian es y p o eso es, con el obje i o de encon a aquellos
pun os que m´as cues an a los es udian es de los p ime os cu sos de in o m´a ica. Es e a ´ıculo
llega a la conclusi´on de que muchos alumnos desa ollan concep os supe iciales sob e la p o-
g amaci´on (dominan la sin axis de cie o lenguaje de p og amaci´on y dominan ins ucciones
aisladas) pe o allan al in eg a es o en p og amas comple os que esuel an un p oblema.
Adem´as, los esul ados de la encues a asegu aban que los concep os que m´as di ´ıciles esul-
aban e an di idi un p og ama en subp og amas, pun e os, ecu si´on y ipos abs ac os de
7
da os (TADs). En cuan o a m´e odos de ap endizaje, el p e e ido es basa se en p og amas de
ejemplo, y des acan los m´e odos p ´ac icos sob e los e´o icos, aunque la eo ´ıa sea ambi´en
impo an e.
En odo caso, en ende las es uc u as de da os y los algo i mos m´as b´asicos es imp es-
cindible pa a cualquie es udian e de in o m´a ica. En p ime luga , conoce los pe mi e oma
la mejo decisi´on de dise˜no en e a un p oblema en cuan o a e iciencia y simplicidad. Pe o,
m´as all´a de es o, en ende su uncionamien o en p o undidad pe mi e pode implemen a
modi icaciones de los mismos. Es o si e pa a adap a los a p oblemas conc e os en los que
las es uc u as o algo i mos necesa ios di ie en en alg´un pun o de los que se es udian como
base, pe o la idea subyacen e es simila y puede se usada pa a esol e dicho p oblema.
I o mando es a capacidad pa a pensa en qu´e usa pa a esol e el p oblema, as´ı como
hace que el ap endizaje sea g adual y comenza po c´odigos sencillos, es lo que puede expli-
ca que se es udien algo i mos que no se usan al ene ya implemen aciones mejo es (aunque
hay una discusi´on sob e si la sencillez de c´odigo jus i ica su ense˜nanza en e a ine iciencia e
inu ilizaci´on del mismo en el a ´ıculo [12]). En muchos cen os se man iene la ense˜nanza de
los algo i mos de o denaci´on de complejidad cuad ´a ica O(n2). An e una p ime a ap oxima-
ci´on, es in e esan e comp ende es os algo i mos pa a despu´es pode pasa al es udio de los
algo i mos ´op imos en cuan o a complejidad O(nlog n), pe o menos in ui i os.
En cualquie caso, no hay duda de la impo ancia de las asigna u as elacionadas con es-
os concep os. Pa a muchos es udian es, la mejo o ma de en ende el uncionamien o de un
algo i mo es e la aplicaci´on del mismo a un caso conc e o, lo que hace mucho m´as in ui i o
el c´odigo asociado y pe mi e, incluso, que no sea necesa io memo iza lo en absolu o. Es o se
elaciona con el a ´ıculo [11], donde no des aca especialmen e el m´e odo de ap endizaje de
isualizaciones in e ac i as, pe o iene una buena acep aci´on (3.3 sob e 5, en l´ınea con o os
m´e odos a excepci´on del ya mencionado uso de p og amas de ejemplo). Su gen as´ı in e e-
san es aplicaciones que mues an el lujo de cie os algo i mos o la isualizaci´on de algunas
es uc u as de da os: en [13] se p esen a un isualizado de es uc u as de da os a ni el con-
cep ual (po ejemplo, los ´a boles se p esen an de la o ma esquem´a ica habi ual en luga de
mos a el con enido de la memo ia del o denado ). El usua io puede ealiza acciones sob e
es as es uc u as de da os y ap ecia c´omo an cambiando de o ma concep ual. En de ini i a,
su gen aplicaciones que apo an un eedback mucho m´as isual que he amien as ´ıpicas de
depu aci´on de c´odigo (debugging).
Todo es o ha se ido de mo i aci´on pa a implemen a un juego (con m´as ca ga educa i a
que l´udica) que explique algunos de los algo i mos b´asicos y es uc u as de da os p incipales
de las ciencias de la compu aci´on. La in enci´on es simula la aplicaci´on del algo i mo sob e
un caso conc e o y alea o io de en ada, siendo el usua io el que hace acciones simila es a
las que ha ´ıa un o denado en ese caso conc e o. Po ejemplo, pa a o denaci´on po inse ci´on
pod ´ıamos pensa que la ase en la que se hace hueco al elemen o a inse a consis e en que
el alo de una posici´on se desplaza a la posici´on siguien e, cuando ealmen e se ob iene el
alo de la posici´on iy se copia en la posici´on i+ 1. Es o, de o ma in e ac i a, se puede
modela haciendo click en dicha posici´on iy a as ando a la posici´on i+ 1, lo que copia ´ıa
el alo . Es as me ´a o as cla amen e no in e ienen en la comp ensi´on del algo i mo (se ´ıa
simplemen e una peque˜na abs acci´on), y podemos deci que el usua io es ´a haciendo acciones
simila es a las que ha ´ıa el o denado sob e su memo ia. Con la desc ipci´on dada, el juego se
engloba ´ıa en el g´ene o de juegos de l´ogica o puzzles.
8
Cap´ı ulo 2
Algo i mos e In e acci´on
2.1. In oducci´on
En es e cap´ı ulo se explica ´a la in e acci´on pedida en cada uno de los juegos implemen-
ados en la aplicaci´on, eco demos: o denaci´on po inse ci´on, o denaci´on po el m´e odo de la
bu buja, o denaci´on po selecci´on, o denaci´on po mezclas (pa e de la mezcla de dos lis as
o denadas) y ´ecnica de la en ana deslizan e. Pa a cada uno de ellos, se mues an las ideas
que ansmi e el u o ial asociado en el juego y se explica la in e acci´on eque ida, ponien-
do ambi´en un ejemplo. El dise˜no y es uc u a global de la aplicaci´on, jun o con diag amas
UML, se explica en el siguien e cap´ı ulo; se deja es e pa a lo espec´ı ico de los algo i mos
implemen ados. Adem´as de lo mencionado, se explica pa a cada juego c´omo se ha ealizado
el con ol del lujo; es deci , el con ol del a ance de la simulaci´on del algo i mo po pa e del
usua io, as´ı como el con ol de la consis encia del modelo in e no en odo momen o espec o
a la is a, es o es, espec o al es ado de la es uc u a de da os mos ada en la pan alla.
Se ha in en ado que odas es as im´agenes que se adjun an cub an lo mejo posible odas
las opciones y di e en es in e acciones de la aplicaci´on. En pa icula , se in en a mos a en
es a memo ia an o los di e en es ex os sin pis as ac i as como aquellos en los que se han
ac i ado las pis as (es a ´ecnica de adap aci´on de la di icul ad se explica con de alle en el
cap´ı ulo 3).
Pa a e ambi´en la de ecci´on an o de in e acciones e ´oneas como de in e acciones co-
ec as o las di e en es pun uaciones esul an es en unci´on de los acie os y allos du an e
el juego y del iempo empleado, se adjun a aqu´ı un ´ıdeo conjun o de oda la expe iencia
en la aplicaci´on sob e la pa e de los u o iales y de los algo i mos. A lo la go del ´ıdeo se
incluyen acciones inco ec as pa a mos a la ac i aci´on de las pis as. El ´ıdeo es ´a disponible
en h ps://you u.be/K PyXDBppLQ
An es de pasa a analiza cada algo i mo, una obse aci´on que ald ´a pa a odos los
juegos es que las posiciones de los a ays se inicializan con alo es alea o ios en e -99 y 99.
En el caso de o denaciones, el usua io end ´a que o dena es os alo es de meno a mayo
simulando el algo i mo que es ´e p ac icando; en el caso de la ´ecnica de la en ana deslizan e,
se ope a con sumas y es as de los alo es, ya que se ilus a la ´ecnica median e el p oblema
de ob ene la suma m´axima de kelemen os consecu i os del a ay.
15

2.2. O denaci´on po inse ci´on
En o denaci´on po inse ci´on, uno de los p ime os algo i mos es udiados, se dis inguen
es ases en el juego, as´ı como las es e apas asociadas en el algo i mo que comp ueba
que el usua io in e acciona co ec amen e. Es e algo i mo pe enece a o denaci´on na u al: se
ealizan menos ope aciones cuan o m´as o denado es ´e inicialmen e el a ay. La complejidad
es O(n2).
Figu a 2.1: Diag ama de lujo co espondien e a o denaci´on po inse ci´on, con ano aciones
sob e la in e acci´on eque ida.
2.2.1. Tu o ial del juego
Se in en an ense˜na las bases del algo i mo y de la in e acci´on pedida con las siguien es
e apas del u o ial:
An es de en a en las ases del algo i mo, se in oduce o denaci´on po inse ci´on. Se
dis inguen dos pa es en el a ay, una p ime a que siemp e es ´a o denada (inicialmen e
con el p ime elemen o, y es ´a indicada en el juego usando colo e de) y una segunda
pa e sin es a necesa iamen e o denada (indicada en el juego en colo blanco). Se indica
que la in enci´on es, en odo momen o, inse a den o de la pa e o denada el p ime
elemen o de la segunda pa e, has a que el a ay quede comple amen e o denado.
16
Figu a 2.2: Ideas b´asicas iniciales en el u o ial de o denaci´on po inse ci´on.
En la siguien e e apa del u o ial, comienzan las animaciones que explican las es ases
que se epi en en el algo i mo y los es ipos de in e acci´on usados en el juego.
1. Elegi la siguien e posici´on a inse a y gua da la en una a iable auxilia .
En la e apa 1 se pide al usua io busca la siguien e posici´on cuyo alo se inse a ´a en la
pa e o denada del a ay, y a as a dicha posici´on a la a iable auxilia ( ep esen ada
po una posici´on sin da os y colocada en el juego ue a del a ay). Se explica que es e
paso es pa a e i a pe de el alo a inse a , ya que a a se sob esc i o.
Figu a 2.3: Paso 1: gua da el alo de la posici´on a inse a den o de la a iable auxilia .
La animaci´on mues a el p oceso de a as a la posici´on con el alo -9.
2. “Hace hueco” en la pa e o denada del a ay al elemen o a inse a . En es e
segundo paso se pide a as a , mien as sea necesa io, la posici´on j−1 a la posici´on
jpa a copia el alo del a ay en una cie a posici´on a la siguien e. Es e p oceso,
aco de con el algo i mo, se ealiza comenzando po la posici´on i(siendo ila posici´on
del elemen o a inse a ) y yendo hacia el comienzo del a ay ( isualmen e, hacia la
izquie da). Se a indicando la posici´on ac ual en colo ama illo pa a hace m´as isual
el p oceso.
17
Figu a 2.4: Animaci´on que a as a la posici´on 0 a la 1 pa a eplica el alo 75. Es necesa io
es e desplazamien o po que −9<75. Se pie de el alo -9 del a ay, pe o se man iene isible
en odo momen o en la a iable auxilia .
3. Inse a el elemen o en la pa e o denada. Cuando en el segundo paso se llegue a
un elemen o que ya es meno que el elemen o a inse a o se alcance el inicio del a ay,
la segunda ase e mina (n´o ese que puede ocu i que la e apa 2 sea ac´ıa). En ese
momen o, pod emos inse a o denadamen e el alo co espondien e a la e apa 1 de
o ma que la p ime a pa e del a ay (ya o denada) c ece una unidad. Pos e io men e,
el p oceso uel e a la e apa 1. La in e acci´on pedida es a as a la a iable auxilia a
la posici´on donde se debe inse a el alo (es deci , donde se ha ealizado hueco).
Figu a 2.5: Animaci´on a as ando el alo de la a iable auxilia hacia la posici´on 0 de la
pa e o denada (la co ec a en es e caso), copiando el alo o igen en la posici´on des ino y
log ando po an o que la pa e o denada del a ay c ezca en una unidad.
2.2.2. In e acci´on de allada con un ejemplo
El u o ial mues a las ideas b´asicas del algo i mo y de la in e acci´on pedida, pe o eamos
la in e acci´on de o ma m´as de allada, ya con un ejemplo en el que se e a al usua io a simula
el algo i mo a pa i de un inpu alea o io. Se in en an aba ca odos los posibles eedbacks
de odas las e apas, po lo que en las im´agenes siguien es se ha p o ocado la ac i aci´on y
desac i aci´on de las pis as pa a mos a los di e en es ex os.
18
Figu a 2.6: Paso 1: Lle a la siguien e posici´on a inse a a la a iable auxilia .
Figu a 2.7: Paso 2: Desplaza copiando pa a hace hueco al 61 en la pa e o denada ( ex o
sin pis as).
19
Figu a 2.8: Paso 2: Desplaza copiando pa a hace hueco al 61 en la pa e o denada ( ex o
con pis as).
Figu a 2.9: Paso 3: A as a la a iable auxilia a la posici´on co ec a pa a copia el alo ,
y log a un suba ay o denado de 2 posiciones. El p oceso ol e ´ıa a empeza , eniendo que
inse a el alo -50 en la pa e o denada.
20

Un ´ul imo comen a io es que si la ase 2 es ac´ıa (no hacen al a desplazamien os), en onces
no se pide ninguna in e acci´on en es a ase. Las pa es 1 y 3 pe manece ´ıan iguales, aunque
en es e caso sean acciones innecesa ias al es a gua dando un alo en una a iable auxilia
e inmedia amen e ecupe ando el alo . Se ha implemen ado as´ı po homogeneidad y pa a
omen a la idea de ac ua de o ma me ´odica.
2.2.3. Algo i mos de con ol y comp obaci´on
El modelo se co esponde con la clase Inse ionSo Manage , que se comunica p inci-
palmen e con A ayPosInsSo y que iene los siguien es a ibu os y m´e odos.
A ibu os.
• alues:A ay con los alo es a o dena , que se a modi icando aco de a las ac-
ciones del usua io.
•s epNumbe : N´ume o de e apa en que se encuen a el p oceso.
•nex Posi ionS ep1: En e o que indica la siguien e posici´on a inse a en la pa e
o denada.
•numbe ToInse : Valo a inse a en la pa e o denada.
•mo esS ep2: N´ume o de acciones eque idas en el paso 2. Se conside a acci´on de
la segunda e apa a cada uno de los desplazamien os de una posici´on a la siguien e
pa a copia el alo .
•comple edS ep2: Acciones ya comple adas en el paso 2.
•posS ep3: Posici´on del a ay donde inse a el alo en la e apa 3.
M´e odos.
•M´e odos de inicializaci´on, ge yse .
• es a (): Reinicia los alo es pa a empeza un nue o juego. La e apa pasa a se
la 1, la siguien e posici´on a inse a pasa a se la segunda (posici´on 1) e indica
ambi´en que no se ha comple ado ning´un paso en la e apa 2.
•s ep1Comple ed(): Debe se llamado cuando el usua io comple a con ´exi o la
e apa 1. Recalcula y ac ualiza sus a ibu os, cambiando s epNumbe al alo 2,
gua dando el alo que hay que inse a en el a ibu o numbe ToInse , calcu-
lando la posici´on donde hay que inse a ese alo (median e el m´e odo p i ado
indPosToInse () que se explica m´as adelan e) y calculando po ´ul imo el n´ume-
o de desplazamien os necesa ios, usando la di e encia en e la posici´on po la que
se encuen a el p oceso de o denaci´on y la posici´on en la que hay que inse a el
alo , es deci , nex Posi ionS ep1 - indPosToInse (nex Posi ionS ep1).
Se usa una a iable auxilia pa a e i a los c´alculos edundan es que p o oca ´ıa
llama a la unci´on indPosToInse () dos eces.
•s ep2Posi ion(): Indica la siguien e posici´on con la que se debe ´ıa in e acciona
en la e apa 2.
•subS ep2Comple ed(): Debe se llamado as cada mo imien o co ec o del usua-
io en la e apa 2. Ac ualiza sus a ibu os, como el a ay alues. Inc emen a el
a ibu o del n´ume o de desplazamien os ya comple ados en la e apa 2 y, de o ma
an´aloga, dec emen a el n´ume o de desplazamien os es an es.
21
•s ep2Comple ed(): Debe se llamado as comple a oda la e apa 2. Ac ualiza sus
a ibu os indicando que la e apa es aho a la e ce a, e inicializando el n´ume o de
desplazamien os comple ados en la e apa 2 a ce o, de ca a a la siguien e i e aci´on.
•s ep3Comple ed(): Llamado as comple a la e apa 3. Recalcula los a ibu os,
ac ualizando el a ay median e alues[posS ep3] = numbe ToInse ; y de ol-
iendo el es ado a la e apa 1.
• inished(): De uel e un alo bool que indica si el p oceso de o denaci´on ha
e minado. Bas a compa a si se es ´a en la e apa 1 pe o la siguien e posici´on
a inse a coincide ya con la longi ud del a ay (es e ama˜no iene dado como
cons an e en la clase U ili ies).
• indPosToInse (): M´e odo p i ado que ayuda a ecalcula los a ibu os as
inaliza la e apa 1. Se ealiza una b´usqueda desde una cie a posici´on o igen del
a ay hacia el comienzo del mismo, has a que se alcanza el inicio de la es uc u a
o has a que se encuen a una posici´on al que su alo es meno o igual que el
alo de la posici´on o igen. Es deci , es e m´e odo calcula la posici´on obje i o a la
que iene que llega el siguien e elemen o a inse a .
Figu a 2.10: C´odigo del m´e odo p i ado indPosToInse ()
.
2.3. O denaci´on po selecci´on
O o de los algo i mos de complejidad cuad ´a ica es la o denaci´on po selecci´on. Tambi´en
se dis ingue en e una pa e inicial o denada (inicialmen e ac´ıa e indicada en el juego en
e de) y el es o del a ay (indicado en el juego en blanco); el algo i mo consis e en busca
el m´ınimo de es a segunda pa e e inse a lo en la p ime a pa e, in e cambiando los alo es
de las dos posiciones que in e ienen. Una p opiedad de es e algo i mo es que siemp e ealiza
el mismo n´ume o de ope aciones (con la sal edad de posibles in e cambios “ i iales” (una
posici´on con s´ı misma) que se pod ´ıan e i a ).
La in e acci´on que se pide al usua io en es e juego es, p obablemen e, la m´as sencilla de
odas, como se e ´a a con inuaci´on. Como ya se ha dicho, es a implemen aci´on de o denaci´on
po selecci´on ealiza siemp e el mismo n´ume o de ope aciones. Es o se ep esen a cla amen e
en el eedback que se da al comple a el juego, ya que siemp e se necesi an el mismo n´ume o
de acciones. Sin emba go, es o no debe con undi al usua io: la in e acci´on en es e juego
pe mi e que el usua io acceda al elemen o m´ınimo de la segunda pa e de un is azo, sin
consumi acciones. Es as ope aciones en una compu ado a s´ı hay que ealiza las.
22
Figu a 2.11: Diag ama de lujo de o denaci´on po selecci´on, con ano aciones sob e la in e -
acci´on del juego.
Figu a 2.12: Diag ama de lujo de m´as bajo ni el de o denaci´on po selecci´on, de allando la
ins ucci´on del diag ama an e io swap(a[i], a[posMin(a[i:])]).
23
2.3.1. Tu o ial del juego
En p ime luga , se p esen a una in oducci´on a es a o denaci´on:
Figu a 2.13: In oducci´on del u o ial de o denaci´on po selecci´on.
Una ez comenzado el juego, se p esen an dos opciones de in e acci´on:
1. Si el m´ınimo de la segunda pa e no queda ya en la p ime a posici´on de es a pa e no
necesa iamen e o denada, se busca dicho alo y se a as a a la siguien e posici´on a
o dena :
Figu a 2.14: El m´ınimo de la segunda pa e (al inicio, la segunda pa e coincide con odo el
a ay) es a as ado a la siguien e posici´on a o dena .
2. Si el m´ınimo de la segunda pa e en alguna e apa coincide con su posici´on des ino (es
deci , queda ya o denado), la in e acci´on que se equie e es simplemen e hace click en
esa posici´on:
24
•posSo ed: Posici´on has a la cual se iene segu idad que el comienzo del a ay
es ´a o denado. Es deci , el ango [0,posSo ed) es ´a o denado.
•posBubble: Posici´on del elemen o que hay que in e cambia con su posici´on an e-
io , es deci , con el que hay que in e ac ua en cada momen o.
M´e odos.
•M´e odos de inicializaci´on, ge yse .
•ini ialize(): Inicializa el a ibu o posBubble con ayuda del m´e odo p i ado que
se explica ´a pos e io men e calcula ePosBubble(), pasando como pa ´ame o el
alo U ili ies.LENGTH-1pa a que la b´usqueda se ealice en oda la es uc u a.
•subS epComple ed(): Ac ualiza los a ibu os as cada in e acci´on co ec a, in-
e cambiando alues[posBubble] y alues[posBubble-1]y ecalculando la si-
guien e posici´on con la que in e acciona median e calcula ePosBubble() con el
pa ´ame o adecuado.
•s epComple ed(): Ac ualiza los a ibu os cada ez que el usua io comple a un
eco ido desde el inal del a ay has a el comienzo in e cambiando posiciones.
Tend emos una posici´on adicional o denada, y pa a la siguien e posici´on con la que
hay que in e acciona se lanza una b´usqueda en odo el a ay de nue o median e
calcula ePosBubble().
• inished(): Indica si el p oceso de o denaci´on ha e minado. Se implemen a com-
p obando que la b´usqueda del siguien e elemen o con el que in e acciona llega al
inicio de la es uc u a, es deci , el a ay ya es ´a o denado.
• es a (): Reinicia el modelo, inicializando los a ibu os. Se ac ualiza a 0 la
posici´on has a la cual enemos un suba ay o denado con segu idad.
•calcula ePosBubble(): M´e odo p i ado auxilia que busca desde la posici´on in-
dicada en el pa ´ame o hacia el inicio del a ay el p ime pa de elemen os conse-
cu i os (a, b) al que a > b. N´o ese que es e m´e odo auxilia se usa en muchos de
los an e io men e explicados.
Figu a 2.23: C´odigo del m´e odo p i ado auxilia que pe mi e implemen a muchos de los
m´e odos es an es de es a clase.
2.5. O denaci´on po mezclas (1)
La o denaci´on po mezclas (en ingl´es, me ge so ) es ya un algo i mo ´op imo en cuan o a
complejidad en iempo (O(nlog n)). Es e algo i mo, pe enecien e al g upo de los algo i mos
“Di ide y ence ´as”, ue in en ado po John on Neumann en 1945. Se basa en dos ideas:
31

ecu si´on y mezcla de dos lis as o denadas. En la escena Me geSo 1 del juego se p e ende
que el usua io abaje sob e la mezcla de dos a ays o denados.
En es a escena, al p incipio, se p esen an dos a ays de cua o elemen os ya o denados,
sepa ados en e s´ı. Debajo, se coloca la lis a (inicialmen e en blanco) sob e la que se cons-
ui ´a el a ay o denado esul ado de la mezcla de las dos lis as supe io es.
La in e acci´on consis e en pensa el ´ındice que se lle a en cada lis a en un momen o de e -
minado (aunque es o se indica cla amen e usando colo es). Aho a, se compa a an los elemen-
os de cada lis a en sus espec i os ´ındices (es deci , lis a0[indice0] ylis a1[indice1]).
T as elegi el meno de los dos, dicha posici´on se a as a a la siguien e posici´on a comple a
del a ay in e io .
32
Figu a 2.24: Diag ama de lujo de la mezcla de dos lis as o denadas.
2.5.1. Tu o ial del juego
El u o ial de es e juego explica median e animaciones lo que se ha indicado en la in o-
ducci´on an e io . Inicialmen e se explica el p op´osi o. Despu´es, comienzan las animaciones
que mues an el p oceso.
33
Figu a 2.25: En p ime luga , se in oduce la mezcla de dos lis as o denadas.
1. Ambos ´ındices comienzan en ce o, y se compa an po an o las posiciones iniciales de
ambos a ays. El alo in e io es el que se inse a en el a ay esul ado, median e una
in e acci´on d ag-and-d op como habi ualmen e.
Figu a 2.26: lis a0[indice0] = lis a0[0]= 9 <17 = lis a1[0] = lis a1[indice1],
po lo que se a as a la p ime a posici´on del a ay 0 a la es uc u a esul ado. Se inc emen a
el ´ındice de la p ime a lis a (indice0), indic´andolo en el juego con posiciones en g is ( e
siguien e pun o).
2. Se compa an de nue o los alo es apun ados po los ´ındices co espondien es (uno de
los dos ´ındices iene que habe cambiado). En el u o ial, la animaci´on mues a el
desplazamien o del segundo elemen o, de nue o omando como o igen la p ime a lis a.
34
Figu a 2.27: El u o ial pasa a mos a que indice0 == 1u ilizando una posici´on en g is en
la p ime a lis a. Como 13 <17, la animaci´on mues a que se debe a as a el alo 13 al
a ay esul ado.
3. Pa a ilus a un ejemplo en el que se oma como o igen la segunda lis a, el u o ial
con in´ua un paso m´as.
4. Finalmen e, aunque es muy in ui i o cu´ando a a acaba el juego, el u o ial e mina
con la animaci´on del mo imien o inal, m´as bien pa a pode explica en el ex o asociado
que el p oceso acaba cuando los ´ındices de ambas lis as o igen son iguales a su longi ud:
2.5.2. In e acci´on de allada con un ejemplo
En la subsecci´on an e io ya se han explicado con su icien e de alle las in e acciones
pedidas, usando el ejemplo del u o ial (que es un ejemplo ijo (es deci , no alea o io) y
seleccionado con cuidado pa a se ilus a i o). Sin emba go, pa a e el ex o que se mues a
al usua io du an e el juego, an o en su e si´on sin pis as como en su e si´on con pis as si el
usua io se bloquea en un paso, eamos las dos p ime as in e acciones de o o ejemplo, con
inpu alea o io:
35
Figu a 2.28: P ime a in e acci´on, con el ex o sin pis as: se indica que hay que a as a cie a
posici´on de cie o a ay a las posiciones in e io es.
Figu a 2.29: Segunda in e acci´on, p o ocando que se ac i en las pis as al alla a ias eces:
se indica la posici´on y la lis a con la que se debe in e acciona .
2.5.3. Algo i mos de con ol y comp obaci´on
La inicializaci´on de los alo es en es e caso es lige amen e dis in a al es o: como los dos
a ays a mezcla ienen que es a ya o denados, cada posici´on no se puede inicializa de o ma
indi idual, ya que depende de o as.
La clase co espondien e al modelo de es a pan alla es Me geSo 1Manage , que in e -
acciona p incipalmen e con A ayPosMe geSo 1. Se ha c eado en el modelo la es uc u a
in e ac ionMe geSo 1 pa a encapsula la in o maci´on de la siguien e in e acci´on que se
le pedi ´a al usua io: n´ume o de lis a donde es ´a la siguien e posici´on a inse a , as´ı como el
´ındice de la posici´on. Los a ibu os y m´e odos de Me geSo 1Manage son los siguien es.
A ibu os.
• alues0, alues1: Lis as con los alo es a mezcla .
•index0,index1:´
Indices de las espec i as lis as.
M´e odos.
•M´e odos de inicializaci´on y ge .
•s epComple ed(): Llamado as una in e acci´on co ec a, inc emen a el ´ındice
adecuado.
36

•ge Nex In e ac ion(): De uel e un obje o in e ac ionMe geSo 1 que encap-
sula la siguien e in e acci´on que debe hace el usua io. Se comp ueba si alguna de
las dos lis as ha sido ago ada. Si ninguna de las dos es ´a ago ada, se busca aquella
al que su ´ındice apun a al alo meno . Se adjun a imagen de es e m´e odo.
•ge Nex Index(): De uel e la siguien e posici´on a ellena del a ay esul ado
(index0 + index1).
• inished(): Indica si el p oceso ha e minado, comp obando si el ´ındice de ambas
lis as es igual a su longi ud.
• es a (): Reinicia el juego, inicializando de nue o los a ibu os. Los ´ındices
uel en a 0, y las lis as se c ean con nue os alo es alea o ios.
2.6. T´ecnica de en ana deslizan e
2.6.1. In oducci´on a la ´ecnica
In o malmen e, la en ana deslizan e se pod ´ıa explica como una ´ecnica en la que una
subes uc u a se desplaza po una es uc u a mayo . Po ejemplo, un suba ay que se des-
plaza po un a ay (es deci , en cada caso se ienen en cuen a solamen e cie as posiciones
consecu i as del a ay mayo ); ambi´en pod ´ıa se una peque˜na ma iz que se desplaza po
una ma iz mayo . En de ini i a, la cla e de es a ´ecnica es que en cada mo imien o la sub-
es uc u a solamen e cambia algunas de sus ca ac e ´ıs icas, y no odas, po lo que no hace
al a ecalcula la ope aci´on asociada a la subes uc u a en cada paso, sino hace un c´alculo
inicial y pos e io men e ajus a el c´alculo solamen e eniendo en cuen a los cambios que se
han ealizado.
Expliquemos es o con m´as de alle, usando el ejemplo que se ha implemen ado en el juego:
dado un a ay de longi ud ncuyos alo es son n´ume os en e os, que emos encon a la suma
m´axima de kelemen os consecu i os (pa a k≤n). Una posible implemen aci´on que de uel e
el esul ado co ec o consis e en coge los kp ime os elemen os (posiciones 0 a k−1, ambas
incluidas), suma los e inicializa el m´aximo a es e alo . Pos e io men e, se oman los ele-
men os co espondien es a las posiciones 1 has a la k, se suman y se compa a el esul ado
con el m´aximo inicializado an e io men e, omando como m´aximo p o isional el mayo alo
de en e es os dos. El p oceso con in´ua, calculando en cada caso la suma de kelemen os
consecu i os del a ay subyacen e y compa ando el esul ado con el m´aximo p o isional. Al
inal, ob enemos el esul ado co ec o median e es e algo i mo de complejidad O(n·k). Pe o
es a complejidad se puede educi , ya que se es ´an ealizando muchos c´alculos edundan es:
al pasa de suma las posiciones ihas a k+i−1 (supongamos un ejemplo y un alo de
37
i al que k+isiga en ango) a suma las posiciones i+ 1 has a k+i(ambas incluidas),
solamen e es ´an cambiando en la suma los ´e minos co espondien es a las posiciones i(cuyo
alo desapa ece en la suma) y k+i(cuyo alo no es aba en la suma, y aho a apa ece). Po
an o, la o ma adecuada de implemen a el p oceso se ´ıa hace el c´alculo inicial, pe o despu´es
bas a con es a a la suma ya calculada el alo de la posici´on que deja de se conside ada,
y suma a la suma ya calculada el alo de la posici´on que en a a se conside ada. Podemos
e es o como una en ana (subes uc u a, suba ay) de longi ud k, que aba ca inicialmen e
las posiciones iak+i−1, y que se desplaza una unidad “hacia adelan e”: aho a aba ca las
posiciones i+1 a k+i. Bas a ´ıa en onces es a el ex emo izquie do de la en ana o iginal, y
suma el alo de la posici´on del ex emo de echo de la misma, que ha pasado a conside a se.
La complejidad en es e caso pasa a O(n).
El caso de una ma iz (a ay bidimensional) es simila : al mo e una subma iz una uni-
dad (una ila m´as, una ila menos, una columna m´as o una columna menos), en gene al (sal o
casos ex emos, como conside a una subma iz ila y mo e la po ilas) hay elemen os que
siguen es ando den o de dicha subma iz, mien as que o os s´ı que cambian. Bas a ´ıa hace
el ajus e conside ando los elemen os que deja de aba ca la subes uc u a y aquellos que
pasan a es a aba cados po ella.
Es a ´ecnica ambi´en se puede adap a a p oblemas que no p esen an una elaci´on an
ob ia con la misma: encon a anag amas de cie a palab a den o de un ex o. Si buscamos
anag amas de una palab a de longi ud ken un ex o de longi ud n, se desplaza po el ex o
(que es un a ay de ca ac e es) un suba ay de longi ud k. En es e caso, la ope aci´on asociada
a la en ana es la ecuencia con que apa ecen las le as: inicialmen e se calcula la ecuencia
de apa ici´on de los kp ime os ca ac e es, pe o al desplaza la en ana bas a con es a una
apa ici´on al ca ac e que sale de la subes uc u a, y suma una apa ici´on al ca ac e que
en a. Si las ecuencias de apa ici´on de la en ana coinciden con las ecuencias de apa ici´on
de la palab a de la que buscamos anag amas, hemos encon ado un anag ama, es deci , una
pe mu aci´on de los mismos ca ac e es.
Figu a 2.30: C´odigo Py hon pa a el p oblema de la suma m´axima de kelemen os consecu i os
de un a ay. Se adjun an comen a ios con las e apas que se dis inguen en la in e acci´on.
38
Figu a 2.31: Diag ama de lujo del p oblema de la suma m´axima de kelemen os consecu i os.
Las ano aciones indican las di e en es e apas conside adas y la in e acci´on eque ida.
39
2.6.2. Tu o ial del juego
En p ime luga , se expone el p oblema que ya se ha comen ado, as´ı como los elemen os
con los que se a a in e acciona :
Figu a 2.32: In oducci´on del u o ial del juego.
Al pulsa el bo ´on pa a pasa al siguien e paso del u o ial, se pasa al paso 1 del algo i mo
(se dis inguen dos pasos, donde el segundo iene es sube apas posibles):
1. Hace la suma inicial: el u o ial mues a la animaci´on de suma los p ime os kelemen-
os, a as ando las posiciones al bo ´on e de de “+”.
Figu a 2.33: Hace la suma inicial: se mues a la animaci´on de la suma de las es p ime as
posiciones. En la imagen, ya se han sumado las dos p ime as posiciones (colo e de) y se
es ´a sumando la e ce a posici´on.
2. Desplaza la en ana y compa a las sumas con el m´aximo p o isional. Es a e apa iene
es sube apas, con es in e acciones asociadas:
a) Desplaza la en ana (1): Se mues a la animaci´on que a as a el ex emo izquie -
do de la en ana al bo ´on de la es a, pa a deja de ene en cuen a ese elemen o
en la suma o al.
40
acie o o el e o del usua io; po ´ul imo, el e ce o ac ualiza las ins ucciones seg´un la
e apa del juego y seg´un si se han ac i ado las pis as.
Figu a 3.3: Todas las clases A ayPos implemen an las in e aces que pe mi en hace d ag-
and-d op. Adem´as, he edan de MonoBeha iou , es deci , son sc ip s.
Game. Tipo enume ado con un posible alo pa a cada juego y men´u, con un alo
adicional pa a de ec a e o es.
A ayCon olle yMe geSo 1Con olle . Ges ionan odos los bo ones que compo-
nen el a ay de o ma global. Tambi´en ealizan median e c´odigo las animaciones del
comienzo de cada juego. Me geSo 1Con olle es necesa io po que la dis ibuci´on
que se p esen a en es a pan alla es dis in a al es o. Su m´e odo m´as impo an e es
loca e(), que ecoloca las posiciones a su luga adecuado en la escena as cada acci´on
del usua io.
GameOp ions. Se enca ga de los bo ones de einicio y ol e hacia a ´as de odos los
juegos. Conoce la acci´on que debe ealiza seg´un el pa ´ame o game que ecibe en los
m´e odos es a Selec ed() ybackSelec ed().
SceneCon olle . Ges iona el cambio de escena y el cie e de la aplicaci´on al hace
click en el bo ´on de sali .
O he Op ionsCon olle . Con ola la animaci´on del pop-up del panel de o as opcio-
nes, despleg´andolo u ocul ´andolo seg´un el bo ´on pulsado.
SlidWindowNewMax. Es simila a los sc ip s que ienen los bo ones que con o man el
a ay, es deci , A ayPos(Juego), aunque es e caso es algo excepcional. La az´on es que
en la ac i idad de desplazamien o de en ana hay un elemen o adicional que s´ı admi e
in e acci´on. As´ı, el bo ´on de nue o m´aximo necesi a ene un sc ip con c´odigo que se
ejecu e al se pulsado pa a comp oba si esa in e acci´on es co ec a o no. El c´odigo se
co esponde con su m´e odo newMaxBu onClicked().
ShowS a is ics. Realiza el olcado del ex o de los da os de endimien o al ´a ea de
ex o p esen e en la pan alla de es ad´ıs icas, pa a pode mos a las. Se ayuda del m´e o-
do ge S a is icsTex () de Da aManage , que a su ez iene una ins ancia de Playe
con esa in o maci´on eque ida.
Da aManage . Clase que ges iona los da os de la aplicaci´on. Se implemen a usando el
pa ´on de dise˜no Single on pa a ene una ´unica ins ancia en odo el juego (adem´as,
47

es segu o en e a concu encia). Sus a ibu os son la p opia ins ancia (como en cual-
quie Single on), el lock de p o ecci´on, una a iable bool loaded que indica si ya se
han ca gado los da os (pa a ca ga los una sola ez aunque se eciban m´as pe iciones),
a ias u as pa a la ges i´on de a chi os, a ibu os pa a ges i´on de pun uaciones y de
es ad´ıs icas, a ibu os pa a con ola el sis ema de log y un en e o con el es ado de las
pis as (solamen e se mues an las pis as en el es ado 2). Adem´as iene una ins ancia
de Playe , encapsulando la in o maci´on de un usua io. En la ca ga de da os (m´e odo
loadDa a()) se usa la clase Bina yFo ma e , y es po es o po lo que se ha explicado
unos p´a a os an es que cie as clases son se ializables. Da aManage ambi´en se en-
ca ga de ges iona las es ad´ıs icas de un juego, como la pun uaci´on. Cuando un juego
acaba, el m´e odo gameFinished() indica a la ins ancia de Playe que ac ualice sus
es ad´ıs icas a˜nadiendo las de la pa ida que acaba de e mina . Tambi´en iene m´e odos
des inados al sis ema de log, aunque es os se explica ´an m´as adelan e. Po ´ul imo, es el
enca gado de gua da los da os pa a que la p ´oxima ez que se en e a la aplicaci´on las
es ad´ıs icas sigan disponibles. Pa a es o, de nue o se usa Bina yFo ma e y se gua da
la ins ancia de Playe median e el m´e odo Se ialize().
LoadDa a. Al ab i la aplicaci´on, ejecu a la ca ga de da os, indicando ambi´en al
Da aManage la u a Applica ion.pe sis en Da aPa h.
U ili ies. Clase con cons an es y con algunos m´e odos auxilia es, como comp oba si
dos ec o es ep esen an posiciones ce canas (con cie o ma gen EPS_NEAR) o ans o -
ma una a iable de ipo TimeSpan a segundos.
3.1.2. Diag amas de secuencia de dos p ocesos p incipales
En p ime luga se mues a un diag ama de secuencia ilus a i o pa a el caso de uso
de consul a es ad´ıs icas. Es o pe mi e en ende mejo y complemen a lo expues o en la
secci´on an e io ela i o a las es ad´ıs icas. Po ´ul imo, se ep esen a median e o o diag ama
de secuencia la anidaci´on de las llamadas en el p oceso de comp oba si una in e acci´on del
usua io es co ec a. Se oma como ejemplo el juego de o denaci´on po selecci´on y se mues a
uno de los posibles eco idos (no se conside an en el diag ama las dis in as opciones de
e apas en el juego o in e acci´on co ec a o e ´onea debido a cues iones de espacio).
Consul a es ad´ıs icas. Uno de los casos de uso de la aplicaci´on es consul a las es-
ad´ıs icas del usua io. La cadena de llamadas que se gene a da luga al siguien e diag ama
de secuencia.
48
Figu a 3.4: Diag ama de secuencia pa a el caso de uso de consul a es ad´ıs icas. Se conside an
solo implemen ados dos juegos po cues iones de espacio, pe o las llamadas desde la ins ancia
de Playe segui ´ıan al es o de ins ancias GameIn o(Juego).
Comp oba in e acci´on. O a de las unciones esenciales que debe ealiza la aplicaci´on
es e i ica que las acciones que ealiza el usua io son co ec as. Se adjun a un diag ama de
secuencia co espondien e a una de es as comp obaciones.
49
Figu a 3.5: Diag ama de secuencia de la comp obaci´on de una in e acci´on del usua io en el
juego de o denaci´on po selecci´on. Se conside a solo un eco ido de las dis in as opciones
que se p esen an y se mues a la anidaci´on de las llamadas en el caso en que la siguien e
posici´on no es ´a ya o denada, el usua io in e acciona co ec amen e, el juego no inaliza as
esa in e acci´on y el a ay con el log no se llena al esc ibi una posici´on adicional.
3.2. Feedback p opo cionado y o as uncionalidades
3.2.1. Feedback
Como se ha discu ido analizando a ´ıculos en el cap´ı ulo 1 de es a memo ia, muchos
au o es coinciden en la necesidad de p opo ciona eedback adecuado, as´ı como adap a la
di icul ad del juego a la habilidad del usua io. Po ejemplo, es os emas se discu en en [1],
[6] o [3]. El juego que se p esen a en es a memo ia iene es ipos de eedback de di e en e
na u aleza:
Acie os/E o es: T as cada acci´on, el sis ema in o ma de si la in e acci´on es co ec a
50
o e ´onea median e ex o en la pan alla del juego. In e namen e, se ac ualiza la pun ua-
ci´on que se mues a al inaliza dicho juego y se ac ualiza el modelo de adap aci´on de la
di icul ad din´amicamen e. Es os dos concep os que se acaban de menciona cons i uyen
el es o de o mas de eedback de la aplicaci´on, y se a a ´an a con inuaci´on.
Pun uaciones y es ad´ıs icas: Pa a in oduci m´as componen e l´udico y ´ıpico de
juegos, se inco po an pun uaciones y es ad´ıs icas. Al acaba cada pa ida se mues a el
iempo que se ha a dado en comple a la y una pun uaci´on asociada que depende de
dicho iempo y del n´ume o de acie os y de e o es. Finalmen e, ambi´en se mues a el
n´ume o de acciones necesa ias pa a comple a el juego (es e ´ul imo da o es m´as bien
solo in o ma i o). En cuan o a la pun uaci´on, se busca un equilib io en e con igu a-
ciones iniciales. Si es sencilla, se eque i ´an menos acciones y po an o hab ´a menos
opo unidades de suma pun os, pe o es as con igu aciones sencillas ambi´en debe ´ıan
comple a se en menos iempo, penalizando menos la pun uaci´on. Con igu aciones a-
les que son necesa ias muchas acciones pa a acaba lle a ´ıan a una mayo can idad de
acie os ( ambi´en de allos, segu amen e) pe o ambi´en penaliza ´ıa m´as la pun uaci´on
po el iempo a dado.
Figu a 3.6: Imagen del eedback p opo cionado al e mina un juego, en es e caso o denaci´on
po selecci´on.
Adem´as del sis ema de pun uaciones, se gua dan es ad´ıs icas in e esan es pa a el usua-
io desde el pun o de is a e´o ico. Po ejemplo, pa a cada pan alla se cuen an el n´ume o
de pa idas inalizadas, el n´ume o de acciones eque idas o ales en dichas pa idas o el
iempo o al empleado. Combinando es os da os, podemos mos a al usua io es ad´ıs i-
cas como el n´ume o medio de acciones eque idas en una pa ida. Tambi´en podemos
consegui da os sob e su endimien o, como el iempo medio empleado pa a cada acci´on.
Se ha decidido mos a en la pan alla de “Es ad´ıs icas”, pa a cada juego implemen a-
do, la mayo pun uaci´on conseguida, el n´ume o de pa idas e minadas, la media de
acciones po juego, el iempo o al empleado en dicha pan alla y la media de iempo
empleado en cada acci´on. Si un juego no iene pa idas e minadas, se indica que no
hay da os.
51
Figu a 3.7: Cap u a de pan alla de las es ad´ıs icas mos adas.
Adap aci´on din´amica de la di icul ad: Segu amen e el m´e odo m´as e icaz pa a es e
ipo de aplicaciones. En es e caso, se basa en p opo ciona mayo o meno in o maci´on
en el ex o que se mues a en cada e apa de cada juego. Se puede modela como un dia-
g ama de es es ados, pe o donde solamen e se han implemen ado dos salidas (mos a
pis as o no). El diag ama de es ados es el siguien e.
Figu a 3.8: Diag ama de es ados co espondien e al sis ema de adap aci´on din´amica de la
di icul ad.
En dicho diag ama ap eciamos:
•Es ado “Sin pis as ( ue e)”: Es el es ado inicial. P ime o se e a al usua io a
esol e el p oblema sin pis as. Mien as se acie e, el sis ema pe manece en es e
es ado; an e un e o , el sis ema cambia al siguien e es ado que se a a explica a
con inuaci´on, donde segui ´a sin mos a las pis as a´un.
•Es ado “Sin pis as (d´ebil)”: Se sigue sin mos a ayuda ex a, pe o el usua io ya
ha come ido un allo. An e un acie o, se uel e al es ado an e io men e explicado;
sin emba go, si alla, ya sabemos que ha enido dos allos seguidos. Pa a e i a la
us aci´on del usua io y que se quede bloqueado en alg´un paso, el es ado cambia
52

a “Con pis as” y el ex o se ac ualiza dando m´as in o maci´on, como la posici´on
con la que hay que in e acciona o el mo imien o que hay que ealiza .
•Es ado “Con pis as”: Las ´ul imas dos in e acciones (al menos) han sido allidas.
Las pis as se ac i an y se mues a m´as in o maci´on in en ando que el usua io
encuen e la in e acci´on co ec a. Es o, a su ez, le puede da m´as pis as pa a
en ende la in e acci´on pedida en gene al y con ello el algo i mo en es udio. Si
se acie a, se desac i an las ayudas comple amen e (es o es, se uel e al es ado
“Sin pis as ( ue e)”); mien as se alle, el sis ema se man iene en dicho es ado con
pis as.
Pa a implemen a es o, la clase Da aManage gua da un a ibu o en e o hin sS a e,
donde 0 se co esponde con “Sin pis as ( ue e)”, 1 se co esponde con “Sin pis as
(d´ebil)” y 2 se co esponde con el es ado “Con pis as”. En el cons uc o y an e nue os
comienzos de juegos, como ya se ha comen ado, se inicializa a 0; po o o lado, an e
cada in e acci´on, se ac ualiza el alo de la siguien e o ma. Si se ha ace ado, se pasa al
es ado 0; si no, el es ado se inc emen a en una unidad, con la excepci´on de es a ya en
el es ado 2 (pis as ac i as) en cuyo caso el a ibu o no cambia. Po ´ul imo, el m´e odo de
Da aManage showHin s() indica si se deben mos a las pis as o no: bas a compa a
el a ibu o hin sS a e con el alo 2. En los m´e odos upda eIns uc ions() que se
comen a on an e io men e, el s ing asociado a las ins ucciones adquie e un alo u
o o seg´un lo que de uel e es e m´e odo showHin s().
3.2.2. Log con la in e acci´on
Po ´ul imo, se almacena un a chi o de ex o con oda la in e acci´on del usua io. Es o en
e siones pos e io es del juego pod ´ıa ene u ilidad pa a consegui es ad´ıs icas m´as elabo a-
das. Sin emba go, el obje i o del log en es e abajo es se i de ayuda en las p uebas inales
con usua ios.
Se ecoge la secuencia de acciones ealizadas en cie a pan alla (momen o en que sucede
medido en segundos desde que el usua io en a en la aplicaci´on, se indica si la in e acci´on es
co ec a y ambi´en se egis an o as acciones como el inal o el einicio del juego). Pos e io -
men e, los a chi os se analiza ´an pa a saca conclusiones de los usua ios que pa icipan en
las p uebas.
En cuan o a la implemen aci´on de dicho log, se gua da como a ibu o de Da aManage un
a ay de ipo s ing de LOG_BUFFER_SIZE posiciones. Pa a no es a ac ualizando el a chi o
de ex o as cada acci´on, la in o maci´on de la in e acci´on se a inse ando en dicho a ay;
cuando es e se llena, se aslada al a chi o de ex o, y el ´ındice de esc i u a del a ay pasa de
nue o al alo 0 (no hace al a bo a lo, se a sob esc ibiendo). Una peque˜na conside aci´on
que hay que ene en cuen a al u iliza es e mecanismo es que al ce a la aplicaci´on, se
encuen e donde se encuen e el ´ındice de esc i u a, hay que olca la in o maci´on del a ay
al a chi o de ex o. Pa a pe mi i es o es ´a el m´e odo o ceLogFileUpda e() de la clase
Da aManage . Pa a ca ga y gua da la in o maci´on se usa la clase File de Sys em.IO.
53
Cap´ı ulo 4
E aluaci´on con Usua ios
En es e cap´ı ulo se explican las p uebas de usabilidad lle adas a cabo pa a la aplicaci´on.
Una p ime a secci´on desa olla los p ime os ensayos que se eliza on, con una e si´on de
la aplicaci´on a´un no de ini i a. An e la necesidad de m´e odos m´as iables y an e los malos
esul ados de las p uebas, se dedic´o una ase in e media (mien as se segu´ıa desa ollando la
aplicaci´on y mien as se co eg´ıan algunos e o es que salie on a la luz en dichas p uebas)
pa a in es iga a ´ıculos sob e m´e odos pa a ealiza las p uebas de usabilidad, as´ı como el
an´alisis de las mismas. La eo ´ıa que se encon ´o m´as aplicable al caso de es a aplicaci´on se
expone esumida en la segunda secci´on. La e ce a explica las p uebas inales con usua ios.
Finalmen e, el cap´ı ulo e mina con los esul ados y las conclusiones sob e odo es e p oceso
ealizado ela i o a p uebas de usabilidad.
4.1. P ime as p uebas con usua ios
4.1.1. In oducci´on
Una ez se consigui´o una e si´on es able con cie os algo i mos implemen ados, se pudo
p oba dicha aplicaci´on con dos usua ios pa a de ec a posibles e o es en ases emp anas
del desa ollo ( al aban po a˜nadi uncionalidades y algunos juegos m´as en e a la e si´on
inal). Como se mencion´o al inal del cap´ı ulo 1, el cos e de a egla un e o se inc emen a
conside ablemen e seg´un aumen a el desa ollo de la aplicaci´on y, e ec i amen e, es as p ue-
bas si ie on pa a co egi lo que se es aba haciendo inco ec amen e y segui desa ollando
de o ma adecuada.
Las p uebas se u ie on que ealiza en emo o, lo que iene algunos incon enien es (aun-
que ambi´en en ajas, como que el usua io es ´a en su en o no). Po an o, ue una e aluaci´on
no mode ada pe o s´ı guiada (sc ip ed es ), ya que se le indic´o al usua io lo que en´ıa que ha-
ce . En conc e o, p ime o se les p opo cion´o un guion con los pasos a ealiza y he amien as a
usa . T as es o, los usua ios deb´ıan ellena un cues iona io p e io a la p ueba. Pos e io men-
e, se pod´ıan ija en la lis a de a eas a ealiza en la aplicaci´on (g abando simul ´aneamen e
la pan alla as habe comp obado que el a chi o de log se gua daba co ec amen e en su
disposi i o). Finalmen e, en´ıan que ellena o o cues iona io con las imp esiones que les ge-
ne ´o la aplicaci´on. Como se ealiza on dos p uebas, las espues as cuan i a i as al cues iona io
apenas ienen ele ancia (la mues a es muy peque˜na). Sin emba go, la ase de in e acci´on
con la aplicaci´on as´ı como las espues as cuali a i as y suge encias de mejo a s´ı esul a on
muy ´u iles.
54
El a ´ıculo [27] explica que an o los es s de usabilidad como el game-based lea ning
es ´an ganando impo ancia. Po an o, ambi´en se debe desa olla el dise˜no de dichos juegos
y sus p uebas. Mien as que en el so wa e habi ual el hecho de no come e e o es es bueno,
un ideojuego debe desa ia cons an emen e al usua io, y se uel e abu ido si no se come e
ning´un e o . En de ini i a, aunque es ´a cla o que las p uebas de usabilidad habi uales hay que
modi ica las pa a ideojuegos y, en conc e o, pa a juegos se ios educa i os, en es a p ime a
ase de las p uebas no se in odujo ninguna dis inci´on. Es a ue o a az´on po la que se
decidi´o hace un segundo conjun o de p uebas de usabilidad.
4.1.2. P uebas ealizadas
Los dos usua ios que pa icipa on en las p uebas en´ıan ya conocimien os de p og ama-
ci´on. En la e si´on que p oba on, e a el usua io el que eleg´ıa si que ´ıa ene pis as o no (es o
se cambi´o m´as adelan e al sis ema de es es ados ya mencionado, as conoce la de ensa
que ealizaban di e sos a ´ıculos cien ´ı icos del eedback pe sonalizado y de la adap aci´on
din´amica y au om´a ica de la di icul ad). En es a e si´on an igua que se us´o en las p ime as
p uebas, uno de los usua ios ealiz´o la p ueba sin ayuda de las pis as, mien as que el o o
pod´ıa consul a las pis as en odo momen o. Las p uebas es aban pensadas pa a ealiza se
en un iempo de en e 15 y 20 minu os. Las a eas del guion se p esen a on en o ma de a-
eas di ec as (solamen e se in o ma de lo que iene que hace , en con aposici´on a las a eas
escena io que a˜naden un con ex o). Los usua ios ealiza on la e aluaci´on con sus disposi i os
m´o iles as p opo ciona les el a chi o .apk de la aplicaci´on.
T as hace el cues iona io inicial, pone en ma cha las he amien as de g abaci´on y com-
p oba que el log se gua da co ec amen e, el usua io pod´ıa comenza con las a eas, que
consis ´ıan en juga 4 pa idas de cada uno de los siguien es juegos: o denaci´on po inse ci´on,
m´e odo de la bu buja, o denaci´on po selecci´on y o denaci´on po mezclas (1). Adem´as, el
usua io deb´ıa comp oba sus es ad´ıs icas en el juego. T as inaliza , en´ıa que comple a la
encues a inal dando sus imp esiones y en ia los esul ados.
4.1.3. Resul ados y posibles mejo as
Aunque no e a un n´ume o de usua ios signi ica i o pa a esul a i os cuan i a i os, s´ı se
ob u ie on suge encias de mejo a, as´ı como posibles cambios en la aplicaci´on as analiza
las g abaciones:
Un e o obse ado en es as p uebas ue la p ecisi´on en el pa ´on d ag-and-d op. El
usua io hac´ıa muchos mo imien os que e an co ec os pe o el sis ema los de ec aba
como inco ec os. Es e p oblema se conside a como c ´ı ico. Hab´ıa apa ecido en ases
iniciales del desa ollo, pe o as ajus a el alo de la a iable asociada a la p ecisi´on,
qued´o sol en ado. M´as adelan e, se descub i´o un e o asociado en el c´odigo. T as
soluciona lo, el p oblema despa eci´o en las segundas p uebas.
En o denaci´on po inse ci´on, en la p ime a implemen aci´on ealizada, hab´ıa una ase
en que desapa ec´ıa de la pan alla el elemen o a inse a , ya que en la ase de hace
hueco a dicho elemen o e a solapado al hace la copia. Es o despis ´o a los usua ios.
En la e si´on inal se incluye la a iable auxilia ya mencionada pa a ene disponible
en odo momen o cualquie elemen o. Adem´as, es o es iel a c´omo ac ´ua ealmen e el
algo i mo.
55
Los usua ios coinciden en que e a necesa ia una p ime a pa e de eo ´ıa (quiz´as incluso
con pseudoc´odigo) pa a e i a el p oceso inicial de p ueba y e o . Po es o, pa a que la
aplicaci´on sea au ocon enida, se implemen a un u o ial guiado que se despliega cuando
el usua io en a a la pan alla de un juego.
Un usua io epo a que en algunos casos el sis ema de in e acci´on pod ´ıa se di e en-
e a d ag-and-d op. Po ejemplo, al in e cambia elemen os se ealiza a as ando un
elemen o conc e o al o o. Es o hac´ıa pensa al usua io que un elemen o iene mayo
je a qu´ıa que el o o, cuando es o no es as´ı.
Tambi´en se encon ´o alg´un aspec o que esul ´o especialmen e ag adable a los usua ios:
el uso de colo es en los bo ones pa a da cie os eedbacks ue bien enido, po lo que se
gene aliz´o el uso de es a ca ac e ´ıs ica en el desa ollo pos e io .
Aunque es o no lo epo ´o ning´un usua io, en el an´alisis de las g abaciones se ap ecia-
ba que en ocasiones el usua io comienza una acci´on, pe o obse a que es una acci´on
inco ec a an es de inaliza la, po lo que de uel e el bo ´on a su posici´on inicial. Sin
emba go, el juego lo de ec a como in e acci´on e ´onea y penaliza la pun uaci´on. Quiz´as
es o se pod ´ıa dis ingui de alguna o ma, de mane a que si el usua io uel e al es ado
inicial, no se conside e un e o . Se dis ingui ´ıan as´ı es as acciones de las co ec as que
se comple an o almen e y de las inco ec as que se comple an o almen e.
El iempo que emplea on los usua ios en comple a las a eas ue de 20 y de 26 minu os
(poco m´as de lo espe ado). El p oblema de la p ecisi´on con amin´o o almen e el a chi o de
log, ya que en la g abaci´on se ap eciaba que el usua io iba en endiendo los concep os, pe o
segu´ıa allando mucho debido a la p ecisi´on: mo imien os co ec os e an clasi icados como
inco ec os. Es a es o a az´on pa a ol e a ealiza p uebas con una e si´on mejo ada.
La siguien e imagen, co espondien e a los e o es acumulados en el iempo de los usua ios,
mues a que las pendien es de las cu as no bajan, como e a p e isible. Adem´as, el p ocesa-
mien o del log se debe hace ag upado seg´un el juego. Si no, al cambia a uno nue o, ol e ´an
a apa ece e o es, di icul ando mucho la ob enci´on de conclusiones.
Figu a 4.1: G ´a icas de e o es acumulados a lo la go del iempo as analiza los logs de los
usua ios de las p uebas iniciales. Se ap ecia que la pendien e apenas desciende a lo la go del
iempo. La g ´a ica es simila a la de [27], con la di e encia de ano a e o es en ez de e en os,
como se hace en el modelo de es e a ´ıculo. Pos e io men e se encuen a el a ´ıculo [16], que
expone la eo ´ıa de las cu as de ap endizaje. Cu iosamen e, si la m´e ica usada es el n´ume o
de e o es y se oma de o ma acumulada, se pod ´ıa deci que es as g ´a icas co esponden a
e siones de cu as de ap endizaje.
56
El uncionamien o de es e sc ip de an´alisis consis e en gua da en una a iable de ipo
dicciona io el momen o de comienzo de un nue o juego. Se egis an los e o es y acie os en
ese juego en in e alos empo ales a pa i de ese ins an e inicial.
Es muy ilus a i a la e oluci´on de la asa de e o es a lo la go del iempo en el caso de
o denaci´on po inse ci´on, que adem´as es el juego que m´as acciones egis a y el que los usua-
ios han clasi icado como menos in ui i o. La g ´a ica se adjun a a con inuaci´on, donde se ha
inco po ado la ec a que ap oxima los pun os, usando el m´odulo scipy.op imize. Se ap ecia
una cla a pendien e nega i a, se˜nal de que el usua io es ´a ap endiendo el concep o a lo la go
del iempo. Debajo de es a imagen se adjun a o a g ´a ica con los e o es acumulados. Se
ap ecia una disminuci´on de la pendien e al a anza en el iempo.
Figu a 4.6: Tasa de e o es a lo la go del iempo pa a o denaci´on po inse ci´on, en in e alos
de 10 segundos (es amos po an o an e una cu a de ap endizaje). El eje x ep esen a el
n´ume o de in e alo conside ado, y el eje yindica el an o po uno de e o es. La ec a de
ajus e mues a pendien e nega i a.
Figu a 4.7: E o es acumulados a lo la go de in e alos de iempo, pa a el juego de o denaci´on
po inse ci´on. El eje x ep esen a el n´ume o de in e alo de iempo (igual que en la igu a
an e io ). El eje y ep esen a el o al de e o es.
Po ´ul imo, se adjun a una abla con es ad´ıs icas globales de odos los logs sob e los di-
e en es juegos.
63

Acciones Acie os E o es Tasa de acie os
Inse ci´on 3713 3017 696 81.26 %
Selecci´on 740 617 123 83.38 %
Bu buja 1643 1299 344 79.06 %
Mezclas 729 624 105 85.60 %
Ven ana 1465 1238 227 84.51 %
Cuad o 4.1: Es ad´ıs icas sob e las acciones ealizadas.
La asa de acie os inal es buena en odos los casos, en o no al 80 %. Como e a espe able,
los juegos que han pa ecido m´as complicados son los que ienen meno asa de acie os. La
di e encia no es g ande, pe o an e la g an can idad de acciones egis adas s´ı es ep esen a i a.
64
Cap´ı ulo 5
Conclusiones y abajo u u o
5.1. Conclusiones
El obje i o de es e abajo es c ea una aplicaci´on educa i a que simula el uncionamien o
de algo i mos o es uc u as de da os y que pe mi a la in e acci´on del usua io. Las p uebas
ealizadas al inal del desa ollo demues an que es o ha sido conseguido, ya que an o el
cues iona io inal sob e las imp esiones con la aplicaci´on como el an´alisis de los logs a ojan
esul ados posi i os. La in e acci´on puede esul a di ´ıcil al p incipio, pe o el usua io aca-
ba en endiendo las acciones que ealiza el algo i mo y, as alguna pa ida, puede eplica lo
sin p oblema. Las p uebas ambi´en han demos ado que las uncionalidades adicionales im-
plemen adas ag egan alo a la aplicaci´on, como el sis ema de adap aci´on din´amica de la
di icul ad o el sis ema de pun uaciones.
Po o o lado, en es e abajo se han u ilizado concep os es udiados a lo la go del g a-
do en ingenie ´ıa in o m´a ica. Como es ob io, las asigna u as de algo i mia ienen un g an
peso, aunque se hayan implemen ado algo i mos b´asicos. Po o o lado, el pa adigma de p o-
g amaci´on o ien ada a obje os se ha u ilizado pa a desa olla un c´odigo eu ilizable, po
lo que asigna u as como Tecnolog´ıa de la p og amaci´on o Ingenie ´ıa del so wa e ambi´en
han ayudado al desa ollo de es a aplicaci´on. Pa a las p uebas con usua ios ha sido ´u il la
asigna u a Desa ollo de sis emas in e ac i os, p opo cionando un m´e odo pa a es e ipo de
e aluaciones. Po ´ul imo, es e abajo ambi´en ha se ido pa a ap ende nue os concep os
que no hab´ıan sido a ados a lo la go del g ado. Po ejemplo, el mo o de ideojuegos Uni y,
usando el lenguaje de p og amaci´on C#, que ha esul ado no edoso igualmen e.
5.2. T abajo u u o
La aplicaci´on implemen ada se pod ´ıa mejo a de di e sas o mas. En p ime luga , la
mane a m´as inmedia a es inclui nue os juegos asociados a o os algo i mos. Po o o lado,
se pod ´ıa u iliza el sis ema de pun uaciones pa a c ea una base de da os que omen e la
compe i i idad en el juego, con el ap endizaje asociado. El sis ema de adap aci´on din´amica
de di icul ad ha esul ado e ec i o, pe o no deja de se muy sencillo, po lo que la aplicaci´on
pod ´ıa pe sonaliza se m´as a´un.
O a posible mejo a es amplia la in e acci´on d ag-and-d op, con o as o mas de ealiza
las acciones en el juego. Po ejemplo, si se implemen an ´a boles, una in e acci´on in e esan e
pod ´ıa se inclina el el´e ono hacia el lado co ec o pa a ep esen a que el ´a bol o a pa a
queda equilib ado.
65
Conclusions and u u e wo k
5.3. Conclusions
The aim o his wo k is o de elop an educa ional applica ion ha simula es he low o
algo i hms and eaches he basics o da a s uc u es, allowing use s o in e ac wi h i . The
usabili y es s pe o med a he end o he de elopmen show ha hese goals ha e been
achie ed. Bo h he su ey abou he imp essions o he use s and he log ile analysis show
posi i e ou comes. Ini ially, use s may ind in e ac ion di icul , bu hey unde s and how
algo i hms wo k a e playing a ew games. Fu he mo e, usabili y es s ha e shown ha
addi ional unc ionali ies in he game like he sco e sys em o dynamic adap abili y imp o e
he applica ion.
In addi ion, concep s s udied h oughou he deg ee in compu e science ha e been used.
Ob iously, subjec s abou algo i hms and da a s uc u es a e e y impo an in his wo k,
al hough algo i hms implemen ed in he game a e basic. Objec -o ien ed p og amming pa a-
digm has been used in o de o de elop eusable code, so subjec s like Compu e P og amming
Technology o So wa e Enginee ing ha e played an impo an ole in his wo k oo. In e ac-
i e sys ems de elopmen subjec has been use ul o usabili y es ing, because i p o ides a
me hod o make hese es s. Finally, I ha e lea ned new concep s oo, like Uni y game engine
o C# p og amming language.
5.4. Fu u e wo k
The applica ion ha has been de eloped could be imp o ed in se e al ways. Fi s , new
games abou algo i hms and da a s uc u es could be included in he applica ion. Secondly,
he sco e sys em may be used o c ea e a da abase ha os e s compe i i eness. The dynamic
di icul y adjus men sys em has been e ec i e, al hough i is e y simple and he applica ion
i sel could be e adjus o he needs o each use .
Ano he possible imp o emen o he game is o ex end d ag-and-d op in e ac ion pa e n
wi h o he ways o execu ing ac ions. Fo example, i ees we e implemen ed, i would be
in e es ing o allow he use o il he de ice in o de o o a e and balance hem.
66
Bibliog a ´ıa
[1] R. D¨o ne , S. G¨obel, W. E elsbe g, and J. Wiemeye , Se ious Games. Sp inge , 2016.
[2] M. Csikszen mihalyi, Flow: The psychology o op imal expe ience. Ha pe & Row New
Yo k, 1990.
[3] P. Swee se and P. Wye h, “Game low: A model o e alua ing playe enjoymen in
games,” ACM Compu e s in En e ainmen , ol. 3, 07 2005.
[4] B. Sawye and D. Rejeski, “Se ious games: Imp o ing public policy h ough game-based
lea ning and simula ion,” 01 2002. Wood ow Wilson In e na ional Cen e o Schola s,
Washing on, DC.
[5] P. Games and M. Knigh , “Ame ica’s a my,” 2002. C own Publishing G oup, New Yo k.
[6] J. Sinclai , “Feedback con ol o exe games,” 2011. h ps:// o.ecu.edu.au/ heses/380/
(Accessed 13 Decembe 2020).
[7] M. P ensky, “Digi al game-based lea ning,” ACM Compu e s in En e ainmen , ol. 1,
10 2003.
[8] D. Lecle cq, “The 8 Lea ning E en s Model and i s p inciples,” 2005.
h p://www.labse .ne /media/p od/8LEM.pd (Accessed 13 Decembe 2020).
[9] M. D. Kickmeie -Rus and D. Albe , “Mic o-adap i i y: P o ec ing imme sion in di-
dac ically adap i e digi al educa ional games,” Jou nal o Compu e Assis ed Lea ning,
ol. 26, no. 2, pp. 95–105, 2010.
[10] R. Ba le, “Hea s, clubs, diamonds, spades: Playe s who sui muds,” Jou nal o MUD
esea ch, ol. 1, no. 1, 1996.
[11] E. Lah inen, K. Ala-Mu ka, and H.-M. J¨a inen, “A s udy o he di icul ies o no ice
p og amme s,” Acm sigcse bulle in, ol. 37, no. 3, pp. 14–18, 2005.
[12] O. As achan, “Bubble so : an a chaeological algo i hmic analysis,” ACM Sigcse Bu-
lle in, ol. 35, no. 1, pp. 1–5, 2003.
[13] R. S. Bake , M. Boilen, M. T. Good ich, R. Tamassia, and B. A. S ibel, “Tes e s and
isualize s o eaching da a s uc u es,” ACM SIGCSE Bulle in, ol. 31, no. 1, pp. 261–
265, 1999.
[14] D. Diche a and A. Hodge, “Ac i e lea ning h ough game play in a da a s uc u es
cou se,” in P oceedings o he 49 h ACM Technical Symposium on Compu e Science
Educa ion, pp. 834–839, 2018.
67
[15] E. Ha ps ead, B. A. Mye s, and V. Ale en, “In sea ch o lea ning: Facili a ing da a
analysis in educa ional games,” in P oceedings o he SIGCHI Con e ence on Human
Fac o s in Compu ing Sys ems, CHI ’13, (New Yo k, NY, USA), p. 79–88, Associa ion
o Compu ing Machine y, 2013.
[16] B. Ma in, K. R. Koedinge , A. Mi o ic, and S. Ma han, “On using lea ning cu es o
e alua e i s,” in P oceedings o he 2005 Con e ence on A i icial In elligence in Educa-
ion: Suppo ing Lea ning h ough In elligen and Socially In o med Technology, (NLD),
p. 419–426, IOS P ess, 2005.
[17] J. K. Haas, “A his o y o he uni y game engine,” 2014. Wo ces e Poly echnic Ins i u e,
h ps://digi alcommons.wpi.edu/iqp-all/3207/ (Accessed 13 Decembe 2020).
[18] E. Balagu usamy, P og amming in C#: A P ime . McG aw-Hill Educa ion, o h ed.,
2010.
[19] C. Kazimoglu, M. Kie nan, L. Bacon, and L. Mackinnon, “A se ious game o de eloping
compu a ional hinking and lea ning in oduc o y compu e p og amming,” P ocedia -
Social and Beha io al Sciences, ol. 47, pp. 1991 – 1999, 2012. Cyp us In e na ional
Con e ence on Educa ional Resea ch (CY-ICER-2012)No h Cyp us, US08-10 Feb ua y,
2012 h p://www.sciencedi ec .com/science/a icle/pii/S1877042812026742 (Accessed
13 Decembe 2020).
[20] J. M. Wing, “Compu a ional hinking,” Communica ions o he ACM, ol. 49, no. 2,
pp. 33–35, 2006.
[21] J. A. Qualls and L. B. She ell, “Why compu a ional hinking should be in eg a ed in o
he cu iculum,” Jou nal o Compu ing Sciences in Colleges, ol. 25, no. 5, pp. 66–71,
2010.
[22] T. Ba nes, H. Rich e Lip o d, E. Powell, A. Cha in, and A. Godwin, “Game2lea n:
building cs1 lea ning games o e en ion,” ol. 39, pp. 121–125, 01 2007.
[23] A. Cha in, K. Do an, D. Hicks, and T. Ba nes, “Expe imen al e alua ion o eaching
ecu sion in a ideo game,” in P oceedings o he 2009 ACM SIGGRAPH Symposium
on Video Games, pp. 79–86, 2009.
[24] E. B. Cos a, A. M. Toda, M. A. A. Mesqui a, and J. D. B anche , “Dslep (da a s uc-
u e lea ning pla o m o aid in highe educa ion i cou ses),” In e na ional Jou nal o
Compu e and Sys ems Enginee ing, ol. 8, no. 4, pp. 1143 – 1148, 2014.
[25] N. Kau and G. Gee ha, “Play and lea n ds: In e ac i e and game ul lea ning o da a
s uc u e,” In e na ional Jou nal o Technology Enhanced Lea ning, ol. 7, pp. 44–56,
09 2015.
[26] M. Eagle and T. Ba nes, “Expe imen al e alua ion o an educa ional game o imp o-
ed lea ning in in oduc o y compu ing,” SIGCSE’09 - P oceedings o he 40 h ACM
Technical Symposium on Compu e Science Educa ion, ol. 41, pp. 321–325, 03 2009.
[27] P. Mo eno-Ge , J. To en e, Y. G. Hsieh, and W. T. Les e , “Usabili y
es ing o se ious games: Making in o med design decisions wi h use da-
a,” Ad ances in Human-Compu e In e ac ion, ol. 2012, 2012. Hindawi,
h ps://www.hindawi.com/jou nals/ahci/2012/369637/ (Accessed 13 Decembe 2020).
68